图与网络分析

运筹学OperationalResearch,Chapter7图与网络优化GraphandNetworkOptimization,1.图的基本概念2.树3.最短路问题网络最大流问题最小费用最大流问题中国邮递员问题,图论的起源：哥尼斯堡（Knigsberg）七桥问题,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,结论：每个节点关联的边数均为偶数。,LeonhardEuler（1707-1783）,1736年，瑞士数学家欧拉（LeonhardEuler，1707-1783）曾撰第一篇图论论文SolutioProblematisadgeometrianSitusPertinentis（依据几何位置的解题方法），欧拉成为图论的创始人.,现实生活中，我们经常碰到一些现象。如：一群人中有些互相认识，有些互相不认识。又如：某航空公司在50个城市之间建立若干航线，某些城市间有直达航班，而另一些城市间没有直达航班。以上现象的共同内容：一是有研究的“对象”，如人，城市等；二是这些对象之间存在着某种关系：如互相认识，有直达航班等。为了表示这些对象以及对象之间的关系，我们将“点”代表“对象”，“边”表示“对象之间的关系”，引出了“图”这个概念。,第1节图的基本概念,1.图(graph)：由点和边组成，记作G=（V，E），其中V=v1,v2,vn为结点的集合，E=e1,e2,en为边的集合。,注:(1)点表示研究对象；边表示研究对象之间的特定关系。,(2)图区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有线相连。,图7-7,2.图的分类,例1哥尼斯堡桥问题的图为一个无向图。,例2五个球队的比赛情况，,常用的名词和记号说明：,无向图G（graph），有向图D（digraph）,图G或D中的点数：p(G)或p(D)；边数(弧)数：q(G)(q(D),若边e可表示为e=u,v，称u和v是e的端点，也称u和v是相邻的。边e是点u（及点v）的关联边。,如果边e的两个端点相重，称该e为环。,如果两个点之间有多于一条的边，称这些边为多重边。,一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。,以点v为端点的边的数目称为点v的次(degree)，记作dG(v)或d(v)(环边计算两次)。,称次为1的点为悬挂点，悬挂点的关连边称为悬挂边。次为0的点称为孤立点。次为奇数的点称为奇点，次为偶数的点称为偶点。,图7-7,d(v1),d(v2)=3,d(v4)=4,定理1图G=（V，E）中，所有点的次之和是边数的两倍，即,这是显然的，因为在计算各点的次时，每条边被它的端点各用了一次。,定理2任一个图中，奇点的个数为偶数。,有向图：路点弧交错的序列回路起点=终点的路初等路(回路)所有顶点均不同简单路(回路)所有边均不同,无向图：链点边交错的序列圈起点=终点的链初等链(圈)所有顶点均不同简单链(圈)所有边均不同,3.链与路、圈与回路,4.连通图,图G中，若任何两个点之间，至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图。,(b)不连通图,（a）连通图,5.支撑子图,例：,G2为G1的支撑子图,例：,设给了一个有向图，D=（V，A），从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记为G（D）。,例：,6.赋权图,设图G（V，E），对G中的每一条边vi，vj，相应的有一条数wij，则称这样的图G为赋权图，wij称为边vi，vj上的权。,这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，如表示时间、费用、距离等。,例：赋权图,给一个有向图D=(V，A)，在V中指定了一点称为发点（记为vs），而另一点称为收点（记为vt），其余的点叫中间点。对于每一弧（vi，vj）A，对应有一个c(vi，vj)0（或简写为cij），称为弧的容量。通常我们就把这样的D叫作一个网络。记作D=（V，A，C）,7.网络,4,树(tree)：无圈的连通图。,第2节树,2.1树及其性质,例判断下面哪个图形是树。,(a),(b),(c),树的应用：组织结构,在计算机上，Windows操作系统采用树形结构管理文件与目录系统。,化学物质的结构：1857年，数学家ArthurCayley利用树的概念来研究烃的同分异构体。,丁烷C4H10的同分异构体,家谱（familytree）,树的性质：,定理3设图G=（V，E）是一个树，p(G)2，则G中至少有两个悬挂点。,注：p(G)2的树最长路的起点和终点必为悬挂点。,证：,定理4图G=（V，E）是一个树的充分必要条件是G不含圈，且恰有p1条边。,定理5图G=（V，E）是一个树的充分必要条件是G是连通图，并且q(G)=p(G)1。,定理6图G是树的充分必要条件是任意两个顶点之间恰有一条链。,证明必要性因G是连通的，故任两个点之间至少有一条链。如果某两个点之间有两条链的话，那么图G含有圈，这与树的定义矛盾，从而任两个点之间恰有一条链。充分性设图G中任两个点之间恰有一条链，那么易见G是连通的。如果G中含有圈，那么这个圈上的两个顶点之间有两条链，与假设矛盾，故G不含圈，G是树。,树的性质小结:树等价于以下三个条件取其二：连通；无圈；边数=顶点数1。从一个树中去掉任意一条边，则余下的图是不连通的。即树是极小的连通图。在树中不相邻的两个点间添上一条边，则恰好得到一个圈。即树是极大的无圈图。,2.2图的支撑树,定理7图G有支撑树的充分必要条件是图G连通。,支撑树的求法：算法1：破圈法在保持连通性的前提下，逐次破开所有圈（去掉圈的任一条边即可），直到无圈时为止。算法2：避圈法在保持无圈性的前提下，从某一顶点开始，逐次生长边，直到连通（所有顶点都被生长到）时为止。,e2,e1,e5,解：破圈法：,避圈法：,e7,图的支撑树的应用举例,例某地新建5处居民点，拟修道路连接5处，经勘测其道路可修成如图所示。为使5处居民点都有道路可连，问至少要铺几条路？,解该问题实为求图的支撑树问题，共需铺4条路。,v2,城市输电线路的架设问题：今欲将n个城市用电缆连结起来建立一个输电网络。问应如何架设输电线路，才能把n个城市都连结起来，且造价最省（即所用的电缆的总长度最短）？,最小树问题图的权最小的支撑树称为其最小权支撑树（MST，minimumweightspanningtree），简称最小树。,2.3最小支撑树问题,最小树算法：1避圈法：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n1条边为止(n为结点数)。2破圈法：在图中找圈，并删除其中最大边。如此进行下去，直到图中不存在圈。,“贪心”算法.,解避圈法：,1,5,3,2,4,破圈法：,例10已知如图7-18所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,第3节最短路问题,图7-18,最短路问题（shortestpathproblem）：在一个赋权图中，求某一顶点v1到其余各顶点（或另一指定顶点）的最小权路。,E.W.Dijkstra（狄克斯拉）标号算法,基本思想：从起点vs开始，逐步给每个结点vj标号（dj,vi），其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一结点。,路的权（长度）定义为路上各边的权之和。,步骤：给起点v1标号0，v1,重复（2）、（3）直到终点标上号dn,vi，则dn即为v1到vn的最短距离，反向追踪可求出最短路。,0，v1,1，v4,例：,3，v1,0，v1,1，v4,0，v1,1，v4,3，v1,5，v3,0，v1,1，v4,5，v3,6，v2,3，v1,0，v1,1，v4,3，v1,5，v3,6，v2,9，v5,0，v1,1，v4,5，v3,6，v2,9，v5,10，v5,3，v1,0，v1,1，v4,5，v3,6，v2,9，v5,10，v5,12，v5,3，v1,此时终点v8已标号12，v5，则12即为v1v8的最短距离，反向追踪可求出最短路。,v1到v8的最短路为：v1v3v2v5v8。,0，v1,1，v4,5，v3,6，v2,9，v5,10，v5,12，v5,3，v1,例3（农夫过河问题）一个农夫要把一只狼，一只羊和一棵白菜用船运过一条河.但是当人不在场时，狼要吃羊，羊要吃白菜，而且他的船每趟只能将狼，羊，白菜之一运过河.问他应怎样才能在最短的时间内把三者都运过河呢？解：人，狼，羊，菜四种东西的组合共有24=16种,但可能的组合仅有10种。用结点表示所有的状态，可转换的状态之间连一条线：,将G的边赋权1，则农夫过河问题等价地化为在图G中求从人狼羊菜结点到空结点的一条最短路。由Dijkstra算法知，两条最短路为,最优方案：第一步，农夫先带羊到对岸，然后空手回来。第二步，带狼（菜）到对岸，但把羊带回来。第三步，把羊留下，带狼（菜）到对岸，空手回来。最后，带羊到对岸。,练习题P2067.6,0，v1,6，v2,7，v4/v6,9，v7,5，v2,4，v1,6，v2,3，v1,8.5，v6,练习题无向图情形,求网络中v1到v8的最短路。,0，v1,3，v2,1，v1,9，v5,5，v3,6，v2,8，v5,10，v5,11，v9,局限性：Dijkstra算法只适用于所有wij0的情形，当赋权图有向图中存在负权时，则算法失效。,0，v1,1，v1,例：,实际上从v1到v2的最短路v1v3v2，权为1。,由Dijkstra算法从v1到v2的最短路v1v2，权为1。,当vi到vj之间没有弧连接时，令wij,设vs到vj经过vi到达vj，则vs到vj的最短距离为：,迭代：,有负权的最短路算法*,【例】求图7-21中v1到v8的最短路长及最短路线,5,2,7,1,1,5,0,5,2,7,3,1,5,6,0,5,2,7,3,1,5,6,3.3应用举例,例13设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格为：,还已知使用不同时间的设备所需要的维修费用为：,如何制定总支付费用最少的设备更新计划？,分析：点vi表示状态“第i年年初购进一台新设备”，弧(vi，vj)表示第i年年初购进的设备一直使用到第j年年初，权表示第i年年初购进的设备一直使用到第j年年初支付的总费用。这样，设备更新计划问题等价于从v1到v6的最短路。,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,最优更新方案：1.第一年和第三年购置新设备；2.第一年和第四年购置新设备。总费用为53。,第4节网络最大流问题,例图7-23是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj）表示从vi到vj的运输线，权表示这条运输线的最大通过能力。制定一方案使从v1到v6的产品数量最多。,图7-23,1.一般提法设有网络D=（V，A，C），其中C=cij，cij为弧（vi，vj）上的容量，现在D上要通过一个流f=fij，fij为弧（vi，vj）上的流量。问题：如何安排fij可使网络D上的总流量v最大?,2.最大流问题的模型,注：满足约束条件的流称为可行流。,3.基本概念和定理,(1)弧按流量分为,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。前向弧的全体记为.,后向弧：与链的方向相反的弧称为后向弧。后向弧的全体记为.,(2)增广链,(3)截集与截量,(4)流量与截量的关系,任一可行流的流量都不会超过任一截集的容量。,定理8可行流f*是最大流当且仅当不存在关于f*增广链。,最大流最小截定理：网络的最大流量等于最小截量。,4.求最大流的方法标号法,理论依据：,思路：从始点开始编号，寻找是否存在增广链。给vj标号为vi,j，其中vi为前一结点，j为调整量。,例14求图7-25所示网络的最大流。弧旁的数字（cij，fij）。,步骤：给vs标号为vs,+，选与vs关联的流出未饱和弧(vs,vj)，给vj标号vi,j，其中jcsjfsj,vs，4,vs，,把结点集V分为,vs，,vs，4,考虑所有弧(vi,vj)或(vj,vi)，其中viVA,vjVB，若该弧为,vs，,vs，4,-v1，1,重复（2）、（3），依次进行的结局可能为,vs，,vs，4,-v1，1,v2，1,-v2，1,重复（2）、（3），依次进行的结局可能为,vs，,vs，4,-v1，1,v2，1,-v2，1,v3，1,(5)调整。取，令,vs，,vs，4,-v1，1,v2，1,-v2，1,v3，1,vs，,vs，3,此时标号无法进行，当前流为最大流，最大流量为5；最小截（vs，v2），（vs，v2），截量为5。,vs，,vs，3,例图中A、B、C、D、E、F分别表示陆地和岛屿，分别表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出标号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。,分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,分析：转化为一个网络图，弧的容量为两点间的桥梁数。,则问题为求最小截。,答案：最小截为AE，CD，CF,例某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点。这个网络的一部分如图所示。它的各段管道（vi，vj）的流量为cij万加仑/小时，单位流量的费用bij百元/万加仑。弧旁的数字为(bij，cij)。从采地vs向销地vt运送石油，怎样运送，才能得到最大输运量，并且输送费用最小？,第5节最小费用最大流问题,假设已求得该网络的最大流值为F，那么最小费用最大流问题，显然可用以下线性规划模型加以描述：,先用最大流算法算出最大流，然后根据边费用，检查是否可能在流量平衡的前提下调整边流量，使总费用得以减少？如有可能，就进行这样的调整。调整后，得到一个新的最大流。然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。,解决最小费用最大流问题，一般有两条途径。,思路：保持问题的可行性（始终保持最大流），向最优推进。,最大流算法思路类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。,思路：保持解的最优性（每次得到的新流都是费用最小的流），逐渐向可行解靠近（直至最大流时才是一个可行解）。,由于和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。,在这一算法中，为了寻求最小费用增流链，对每一当前流，需建立伴随这一网络流的增流网络Gf。,增流网络的顶点和原网络相同。,按以下原则建立增流网络的边：若G中边(u,v)流量未饱和，即f(u,v)c(u,v)则Gf中建边(u,v)，赋权b(u,v)=b(u,v)；若G中边(u,v)已有流量，即f(u,v)0则Gf中建边(v,u)，赋权b(v,u)=b(u,v)。,3,v2,v3,4,1,2,v1,vt,2,1,6,vs,-1,-1,增流网络Gf,-4,-2,例,建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。,计算中有一个问题需要解决。这就是增流网络Gf中有负权边，因而不能直接应用标号法来寻找vs至vt的最短路径，需要采用其它计算有负权边的网络最短路径的方法来寻找vs至vt的最短路径。,取f(0)=0为初始可行流。,构造增流网络Gf(0)，并求出从vs到vt的最短路。,增流网络Gf(0):,最短路P0=(vs,v2,v1,vt),f(0):,D中最短路P0相应的增广链为,在上进行调整，得f(1),f(0):,f(1):,v1,增流网络Gf(1):,最短路P1=(vs,v1,vt),f(1):,f(1):,与最短路P1相应的增广链,最短路P2=(vs,v2,v3，vt),f(2):,增流网络Gf(2):,f(2):,与最短路P2相应的增广链,最短路P3=(vs,v1,v2,v3,vt),f(3):,增流网络Gf(3):,与最短路P3相应的增广链,f(3):,f(4):,增流网络Gf(4):,增流网络中已不存在从vs到vt的路径，最小费用最大流：,中国邮递员问题（ChinesePostmanProblem，CPP）一个邮递员投递信件必须走遍某街区的所有街道，任务完成后再回到邮局.问他应如何安排投递路线，才能使得所走路线最短？这一问题由我国数学家、山东师范大学数学系原教授管梅谷（KuanMeiKo）先生于1962年首先提出，并给出了一个算法（奇偶点图上作业法），故国际上称为中国邮递员问题。,第6节中国邮递员问题,图论模型：以街道为边，以街口（街道与街道的交叉处）为顶点，以街道的长度为边的权作图G。,6.1一笔画问题,给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这条链为欧拉链。若存在一个简单圈，过每边一次，且仅一次，称这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。,一个图能一笔画出，这个图必是欧拉图（始点与终点相同）或含欧拉链（始点与终点不同）。,定理9连通多重图G有欧拉圈，当且仅当G中无奇点。,直观图：,推论连通多重图G有欧拉链，当且仅当G恰有两个奇点。,割边：设