图论－孟1ppt课件.ppt

数 学 建 模（三）图 论,主要内容：,1、图的基本概念,3、最短路问题,4、最大流问题,5、最小费用流问题,2、最小树问题,6、旅行商问题（点路优化）,7、计划评审方法(PERT)或关键路线法(CPM),8、欧拉图与中国邮递员问题（弧路优化）,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。,对于科学研究，市场和社会生活中许多关于管理、组织与计划中的优化问题，都可以用图论的理论和方法来加以解决。例如，,1、各种通信线路的架设，输油管道的铺设，铁路 或者公路交通网络的合理布局等问题。,2、在企业管理中，如何制订管理计划或设备购 置计划，使收益最大或费用最小问题,前 言,3、在组织生产中，如何使各工序衔接好，才能使生产任务完成得既快又好。,4、在现有交通网络中，如何使调运的物资 数量多且费用最小。,引例1 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图所示。,歌尼斯堡七桥难题,普莱格尔河,当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象 成图1b所示图形的一笔画问题。即能否从某一点 开始不重复地一笔画出这个图形，最终回到原 点。欧拉在他的论文中证明了这是不可能的，因 为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一 个著名问题。,用A、B表示两座小岛，C、D表示两岸，连线AB表示A、B之间有一座桥。,问题简化为：,A,B,C,D,在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点,七桥问题的数学模型：,判断是否为欧拉图?,因为d(A)=5为奇数，,不是欧拉图,七桥问题的答案：,否,引例2 一笔画问题及中国邮路问题,中、日、口、串、田、目,田,日,中,白,回,不连通,可一笔画,可一笔画,不可一笔画,可一笔画,可一笔画,不可一笔画,不可一笔画,一笔画问题：,1、一个连通图的顶点都是偶点，没有奇点，则该图 可以一笔画出,2、一个连通图的顶点恰有两个奇点，其余均为偶点，则从任一奇点出发，可以一笔画出该图，而终点 则是另一个奇点。,（从任一点出发均可）,3、一个连通图的顶点有两个以上的奇点，则该图 不能一笔画出,中国邮路问题(弧路优化）,提出问题的人：管梅谷教授,时间：1962年,提出的问题：,一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？,在G上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小,结论：选择最佳投递路线=选择重复边的权和最小的路线,第一节 基本概念,1、图由若干个点和连接这些点的边所组成的图形。（G）,2、节点（顶点）图中的每个点。（）,边节点间的连线,或,弧标有方向的边,3、前向弧：对节点P,进入点P的弧 后向弧：离开点P的弧,点和边无向图,点和弧有向图,4、链：一个点与边的交错序列（要求相邻节点 间有边或弧相连）,开链,闭链,5、路：对有向图，称链 为以 起点，为终点的路。,回路：首尾相接的封闭路,圈：首尾相接的封闭链,6、网络：在图的边或弧上，标上某种数量指标。,权,链不一定是路，但路一定是链。圈不一定是回路，但回路一定是圈。,权可代表范围、距离、容量、时间等,二节点构成的边的长度用,容量指标：,实际流量：,图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。,7、连通图：图中任何节点间皆有链相连,连通片：图中任何连通的一部分,连通图,不连通图,8、树及其性质,定义 连通且不含圈的无向图称为树,G1,G2,G3,树,树叶,分枝点,树枝,不是树,森林,部分树：若连通图G的部分图是一棵树，则 称 之为G的部分树。,最小部分树：图G的所有部分树中，边长总和最小者。,G的生成树,定理2 设G是具有n个顶点的图，则下述命题等价：,1)G是树（G无圈且连通）；,2)G无圈，且有n-1条边；,3)G连通，且有n-1条边；,4)G无圈，但添加任一条新边恰好产生一个圈;,5)G连通，且删去一条边就不连通了（即G为最,最小连通图）；,6)G中任意两顶点间有唯一一条路.,例 有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来。,从以上的例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。,本章应用：,1、最短路问题,2、最大流问题,3、最小费用流问题,第二节 应用举例,4、最小树问题和旅行商问题,最短路问题,主要内容及应用：,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解.,最短路问题的两种方法：Dijkstra和Floyd算法.,1)求赋权图中从给定点到其余顶点的最短路.,2)求赋权图中任意两点间的最短路.,二、最短路问题,解决方法：,1、狄克斯屈拉（Dijkstra)算法（标号法）它是在1959年提出来的。目前公认，在所有的权 时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点 到任意一个点 的最短路。,Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。,设节点 到节点 的最短路为,则：必是 到 的最短路。,必是 到 的最短路,基本思想：,表示发点 到 的最短距离的上界,表示发点 到 的实际最短距离,符号记法：,对每一个节点，标号分临时标号（T类标号）和固定标号（P类标号）,1、出发选择距离 最近的节点，假设为；,2、找到与 相关联的所有前向弧节点，若为，则比较当前分别到 的距离，取 最小的确定为固定标号；,3、依次类推，直到所有T类标号都改为P类标号。,基本方法：,首先给发点 标上P类标号，即 其余节点标上T类标号，且,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（1）查与 相关联的前向弧端点有，修改对应的临时标号为,第 1步,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 1步,即节点 获得固定标号,（2）比较（当前所有临时标号）,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 2步,（1）查 与新标号 相连的前向弧节点有,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（2）比较（当前所有临时标号）,第 2步,即节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 3步,（1）查 与新标号 相连的前向弧节点有,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（2）比较（当前所有临时标号）,第 3步,即节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 4步,（1）查 与新标号 相连的前向弧节点有,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（2）比较（当前所有临时标号）,第 4步,即节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 5步,（1）查 与新标号 相连的前向弧节点有,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（2）比较（当前所有临时标号）,第 5步,即节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 6步,（1）查 与新标号 相连的前向弧节点有,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,（2）比较（当前所有临时标号）,第 6步,即节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第7步,（1）查 与新标号 相连,修改 的临时标号为,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,第 7步,节点 获得固定标号,2,2,2,3,3,1,2,2,2,3,2,2,3,1,2,3,2,2,2,1,2,2,2,3,1,2,2,使用Dijkstra应注意：1.可以求任意两点间的最短路。2.最短路不唯一，但最短路值相等。3.弧值非负，只能求最小，不能求最大。,2、Floyd算法,网络D=（V,A,W），令U=(uij)nn，表示 D 中 vi 到 vj 的最短路的长度。,wij 为弧(vi，vj)的权。,考虑 D 中任意两点 vi，vj，如将 D 中 vi，vj 以外的点都删掉，得只剩 vi，vj 的一个子网络 D0，记,适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点v1到所有其它点 vj 的最短距离。,在 D0 中加入 v1 及 D 中与 vi，vj，v1 相关联的弧，得 D1，D1 中 vi 到 vj 的最短路长记为，则一定有,uij(0),u1j(0),ui1(0),再在D1中加入 v2 及 D 中与 vi，vj，v1，v2 相关联的弧，得 D2，D2 中 vi 到 vj 的最短路长记为，则一定有,递推，D 中 n 个点逐个加入子网络，终得 D 中 vi 到 vj 的最短路路长,u2j(1),ui2(1),如果计算结果希望给出具体的最短路的路径，则构造路径矩阵 S=(sij)n n,sij 表示 vi 到 vj 的最短路的第一条弧的终点。,D中vi到vj的最短路,从 vi 到 vj 的最短路的第一条弧为(vi，vt),从 vt 到 vj 的最短路的第一条弧,算法步骤：,第 1 步：,第 2 步：,第 3 步：,当 k=n 时，,其中，元素 uij(n)就是 vi 到 vj 的最短路路长；元素 sij(n)就是 vi 到 vj 的最短路的第一条弧的终点。,解：,（1）用U(0)的第一行、第一列来修正其余的uij，即作,min，4+5,例 求如下网络中各点对间最短路的路长。,添加v1点修改其他任两点之间的最短路,同时，在修正 处修改,（2）用 U(1)的第二行、第二列修正其余的 uij，,（3）用 U(2)的第三行、第三列修正其余的 uij，,2 7 6,（4）用 U(3)的第四行、第四列修正其余的 uij,4 4 4,如果在一行路径终点是一样的,8 0-1 3-54 9 0,（5）用 U(4)的第五行、第五列修正其余的 uij,2 25 5 55 5 5,从 v1 到 v3 的最短路长度,路径：,从 v5 到 v2 的最短路长度及路径？,最短路问题的0-1规划法,设起点为1，终点为n，引入0-1变量xij,弧(i,j)在最短路上，则xij=1，对起点和终点以外的任意一个顶点，如果,说明从i出发的所有弧中必然有一条在最短路上，即最短路经过该顶点，则从其它顶点到该顶点的弧中必然有一条弧在最短路上，所以有,对于1点和n点，则必然满足,0-1规划的最短路模型为,例题Lingo程序,5,6,5,7,5,3,6,4,1,1,4,2,3,练习1、求以下网络图中从顶点 到其余各顶点的 最短路。,5,6,1,1,4,2,求以下网络图中从顶点 到其余各顶点的最短路。,练习2、设备更新问题,某企业使用一台设备，可连续工作4年，每年年初决定是更新机器还是继续使用旧的，若购新的，就要支付一定购置费，若继续使用旧的，则需要支付一定的维修费用，而且随着机器使用的年限，费用逐年增多。问在4年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？,已知设备在4年内各年年初的价格及设备使用不同年数的维修费如下：,1,2,5,3,4,3.5,4.1,3.8,3.6,第一步：(1),1,2,5,3,4,3.5,4.1,3.8,3.6,第二步：,1,2,5,3,4,3.5,4.1,3.8,3.6,第三步：,1,2,5,3,4,3.5,4.1,3.8,3.6,第四步：,定义1:弧的容量 和流量网路流一般在有向图上讨论网络中各弧的最大通过能力称为权，记为 cij，弧上的实际流量记为 fij 图中规定一个发点S，一个收点T节点没有容量限制，流在节点不会存储,三、最大流问题,可行流定义2:满足以下条件的流称为可行流：1、容量限制条件：0fij cij2、平衡条件：对每个节点，流入量流出量,满足上述条件的网路流称为可行流 总存在最大可行流 最大流问题也是一个线性规划问题,定义3 增广路,当支路上 fij=cij，称为饱和弧 当支路上 fij 0的弧,称为非零流弧 若u是连接发点vS和收点vt的一条路,前向弧,记为u+后向弧,记为u-,基本方法:（福特富尔克逊标号法）,基本原理：,找到一条能从发点输送正流到收点的路，利用这条路把尽可能多的流从发点送到收点，重复这个过程，直到再也找不到增广路为止。,ford-fulkerson,标号法具体步骤：,1、标号过程,2、调整过程,寻找增广路,增大增广路流量,检查当前未饱和的前向弧和非零后向弧，反向追踪,选择段数最少的增广路,1,S,T,4,2,3,V(f)=0,V(f)=0,(0,4),(0,3),(0,4),(0,2),(0,1),(0,2),(0,3),(0,3),(0,2),1,S,T,4,2,3,V(f)=0,V(f)=3,(3,4),(3,3),(0,4),(0,2),(0,1),(0,2),(0,3),(3,3),(0,2),第一步：发点s到收点t的最小层数为3.,1,S,T,4,2,3,V(f)=0,V(f)=5,(3,4),(3,3),(2,4),(2,2),(0,1),(0,2),(2,3),(3,3),(0,2),第二步：,1,S,T,4,2,3,V(f)=0,V(f)=6,(4,4),(3,3),(3,4),(2,2),(1,1),(0,2),(2,3),(3,3),(0,2),第三步：,最大流问题的数学规划表示形式：,下面以例为例介绍一下lingo程序,练习3、连接某产品产地v1和销地v6的交通网如下，弧旁数字表示这条运输线的最大通过能力。,试制定一个运输方案，使从v1到v6的产品数量最多。,v2,v5,3,（2,4）,（8,8）,v3,v1,v4,v6,（10,10）,（5,5）,（9,11）,（3,3）,（4,5）,（6,6）,（9,17）,3.4 最小费用最大流问题,网络D=(V,A,C),每一弧(vi,vj)A，给出（vi,vj）上单位流的费用b(vi,vj)0，（简记bij）。,最小费用最大流问题：,求一个最大流 f，使流的总费用 取最小值。,费用最小的另一可行流,费用最小的初始可行流,费用最小的增广链,弧旁数字（Cij，fij，bij）,增加一单位流量时，费用增加多少？,在一个已知某可行流的容量费用网络中如何求得费用最小的增广链？,5.1求解原理,设对可行流f 存在增广链，当沿以=1调整f，得新的可行流 f 时，(显然V(f)=V(f)+1)，两流的费用之差,b(f)-b(f),称为增广链 的费用。,最小费用最大流的求解原理,若f 是流值为V（f）的所有可行流中费用最小者，而 是关于f 的所有增广链中费用最小的增广链,则沿 以去调整 f，得可行流 f，f 就是流量为V(f)+的所有可行流中费用最小的可行流。这样，当 f 是最大流时，f 就是所求的最小费用最大流。,2、如何在已知 f 是流量为V(f)的最小费用流的情况下，求出关于f 的最小费用增广链。,1、初始最小费用流如何求得？,两个问题：,求已知最小费用流的最小费用增广链,构造赋权有向图W(f),它的顶点是D的顶点,W(f)中弧及其权wij 按弧（vi，vj）在D中的情形分为：,则(vi,vj)W(f)，且wij=bij,若(vi,vj)A，且fij=0（零弧），,费用,则(vj,vi)W(f),且wji=-bij,若(vi,vj)A，且fij=cij（饱和弧）,若(vi,vj)A，且0fijcij，,则(vi,vj)W(f)，且wij=bij,及(vj,vi)W(f)，且wji=-bij,新网络W(f)称为流f 的（费用）长度网络。,由增广链费用的概念及网络W(f)的定义，知在网络D中寻求关于可行流f 的最小费用增广链，等价于在网络W(f)寻求从vs到vt的最短路。,5.2最小费用最大流算法,第1步：确定初始可行流f 0=0，令k=0；,第2步：记经 k 次调整得到的最小费用流为f k，构造增量网络W（f k）；,第3步：在W（f k）中，寻找vs到vt的最短路。若不存在最短路(即最短路路长是)，则f k 就是最小费用最大流；若存在最短路，则此最短路即为原网络D中相应的可增广链，转入第4步。,第4步：在增广链上对f k 按下式进行调整，调整量 为,=min,令,得新的可行流 f k+1,返回第2步。,例:求下图所示网络的最小费用最大流。弧旁数字为（bij，cij）。,解:（1）取初始可行流f 0=0；,（2）按算法要求构造长度网络W(f 0)，求出从vs到vt的最短路。,（3）在原网络D中，与这条最短路对应的增广链为=（vs,v2,v1,vt）。,（4）在上进行调整，=5，得f 1，如图(b)所示。,图(i)中，不存在从vs到vt的最短路，所以f 4为最小费用最大流。,练习（最小费用最大流问题）现需要将城市s的石油通过管道运送到城市t，中间有4个中转站，由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图7-8所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费.,返回导航,3.5 最小生成树问题和旅行商问题,3.5.1 最小树问题,1、如何修筑一些公路把若干个城镇连接起来 并使总长度最小？2、如何架设通讯网将若干个需要通话的点连 接起来并使用料最省？3、如何修筑渠道将水源和若干块待灌溉的地 沟通起来并使总长度最短？,问题：,在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；去掉该圈中权数最大的边；反复重复 两步，直到最短树。,常用的有破圈法和生长法（避圈法）两个方法,1、破圈法,2、避圈法,从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数的边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树。,例1、已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。(采用两种方法）,最小树问题的线性规划模型,将最小树问题写成数学规划的形式还需要一定的技巧.设是两点与之间的距离，或1（1表示连接，0表示不连接），并假设顶点1是生成树的根.则数学表达式为:,我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2-10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2-10）都有一条管道相边，并且铺设的管子的量尽可能的少.图7-9给出了SV地区的地理位置图，表7-7给出了城镇之间的距离.,练习1,返回导航,连接这10个城镇的最小距离为60公里，其连接情况如图7-10所示.,图7.10 SV地区的最优连线,旅行售货员问题或货郎担问题.,一个旅行售货员想去访问若干城镇，然后回,到出发地.给定各城镇之间的距离后，应怎样计划,他的旅行路线，使他能对每个城镇恰好经过一次,而总距离最小？,它可归结为这样的图论问题：在一个赋权完,全图中,找出一个最小权的H圈,称这种圈为最优圈.,但这个问题是NP-hard问题，也就是说,对于,大型网络(赋权图),目前还没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好不一定最优）的解.,定义：,设G=(V,E)是连通无向图，包含图G的每个顶点的路称为G的哈密尔顿路(Hamilton路或H路).,包含图G的每个顶点的圈，称为G的哈密尔顿圈,(或Hamilton圈或H圈).,含Hamilton圈的图称为哈密尔顿图(或Hamilton,图或H图).,一个可行的办法:,是先求一个H圈,然后适当,修改,以得到具有较小权的另,一个H圈.,定义 若对于某一对i和j，有,则圈Cij将是圈C的一个改进.,二边逐次修正法:,在接连进行一系列修改之后,最后得一个圈,不能,再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个,程序可以重复几次，每次都以不同的圈开始.这种,方法叫做二边逐次修正法.,例对下图的K6,用二边逐次修正法求较优H圈.,较优H圈:,其权为W(C3)=192,分析:找出的这个解的好坏可用最优H圈的权,的下界与其比较而得出.即利用最小生成树可得最,优H圈的一个下界，方法如下：,设C是G的一个最优H圈，则对G的任一顶点v,C-v是G-v的路，也G-v是的生成树.如果T是G-v的,最小生成树,且e1e2是与v关联的边中权最小的两条,边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界.,取v=v3,得G-v3的一,最小生成树(实线),其,权w(T)=122,与v3关联,的权最小的两条边为,w(T)+w(v1v3)+w(v2v3),=178.故最优H圈的权,v1v3和v2v3,故w(C),应满足178 w(C)192.,旅行商问题的数学表达式：,真题最佳灾情巡视路线的模型的建立与求解,问题转化为在,给定的加权网,络图中寻找从,给定点O出发,行遍所有顶点,至少一次再回,回到点O,使得,总权(路程或时,时间)最小,即,最佳旅行售货,员问题.,当最小生成树问题或旅行商问题顶点的个数较大时，目前比较有效的方法是遗传算法.,