第八章--图与网络.ppt

《第八章--图与网络.ppt》由会员分享，可在线阅读，更多相关《第八章--图与网络.ppt（130页珍藏版）》请在三一文库上搜索。

1、第 八 章 图 与 网 络 分 析,教学目的：让学生了解图论的基本知识，掌握用网络表示所研究问题、对象的基本属性及其解决方法。 教学内容：基本概念、树、最短路、最大流、最小费用最大流等。 教学难点：建立网络图的技巧和各种方法产生的思路。 学时安排：810学时。,第一节 图与网络的基本知识,1、18世纪哥尼斯堡城中普雷格尔河中有两个小岛C、D，它们之间与两岸A、B共有七座桥相连。,一、图论形成的历史回顾,A,B,当地人热衷于这样的游戏：一个人怎样才能一次连续走过七桥且每桥只走一次，再回到出发点。,1736年，著名数学家欧拉把此问题简化为图，并发表了论文：“依据几何位置的解题方法”。,能否从某一点

2、开始不重复地一笔画出这个图形，最终回到原点?,2、1847年，物理学家基尔霍夫为解决有关线性方程组而发展了“树”的理论。他将网络中的电感、电容、电阻等抽象为点和线，得到一简单的组合结构。这种结构便于运算，不必指明为何种元素。,3、1857年，凯莱研究饱和烃链CnH2n+2的同分异构体时，又一次引入树状结构，例如， C4H10 。,5、1857年，英国数学家哈密尔顿发明了一个游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上的20个城市，要求寻找一条路径：由某个城市出发每城市仅去一次，最终回到出发点。,1、有向图与无向图：如果顶点之间的连线皆是无方向的（称为边，边的集合记

3、为E），此时图G称为无向图，记为G=（V，E）； 如果顶点之间的连线有方向，即有向边（或称为弧，弧的集合记为A） ，此时图G称为有向图，记为 D =（V，A）。用m(D)=E（ A）表示图D 中边（弧）的数量；用n(D)=V表示图D中顶点的数量。,一个图是由点集V=vi和V中元素（顶点）之间的连线所组成。,二、图与网络的基本概念,G=（V，E） V=A，B，C，D，N，F，G，H，M E=A,A,A,B,A,C,H,M m(G)=12；n(G)=9,边,端点,端点,D=（V，A） V=M，N，F，G A=M,G,G,F,M,N,N,F,弧,始点,终点,2、如果一条边的两端点相同，此边称为环，两

4、点之间多于一条边的，称为多重边。,3、简单图：无多重边和环的图； 多重图：有多重边，无环的图。,4、链：点、边交替的序列（V1,e1, V2,e2, ,Vi,ei) ； 简单链： 边不重复， A, C, D, B, G,D,N; 初等链： 点、边不重复， A, B, G, F, N; 。,5、 圈：链上首、尾节点是同一节点时，称为圈； 简单圈：圈中没有重复的边；(A,B,G,B,D,C,A) 初等圈：既无重复点，也无重复边;(A,B,D,C,A),路：链上边方向一致时，称为路； 回路：路上首、尾节点是同一节点时，称为回路。,6、顶点的次：以点vi为端点的边数，记为d(vi )。,如图中d(A

5、) =2（用于无向图）。,出次：以点vi为始点的边数，用d+(vi )表示 。 入次：以点vi为终点的边数，用d-(vi )表示。 d+(vi ) +d-(vi )= d(vi )（用于有向图）。,d+(D ) =1 d-(D ) =1 d(D) =2,偶点：d(v) = 偶数； 奇点：d(v)=奇数 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ，无边图,7、连通图：图G=（V,E）中任意两点间至少有一条链。 子图： G=（V,E），其中 VV ，E E。,支撑（生成）子图：对于子图G=（V，E），当V=V时，且与图G=（V，E）的连通性相同的子图

6、称为支撑子图，或生成子图。,8、完全图：任意两点间皆有边相连的无向简单图。,9、基础图：将有向图中弧去掉其方向所形成的无向图，称为原有向图的基础图。 网络：给图的边或点赋予某些数量指标（我们称之为“权”），这种赋权图又称为网络。,10、图的矩阵表示：邻接矩阵与权矩阵,（1）邻接矩阵：图G=(V，E)，V=n，构造一个矩阵邻接矩阵A=(aij)nn，其中,（2）权矩阵：图G=(V，E)，V=n，边（vi， vj)有权ij，构造矩阵权矩阵B=(bij)nn，其中,定理1 任何图中，顶点次的总和等于边数的2倍。,三、基本理论,d(G)=2; d(D)=2; d(N)=2;d(F)=2;,次为奇数的点

7、为奇点，次为偶数的点为偶点。奇点的集合可记为V1，偶点的集合记为V2。,定理2 任何图中，次为奇数的顶点必为偶数个。,四、欧拉回路与道路 定义：连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图（图）。,定理：无向连通图G是欧拉图，当且仅当G中无奇点。,推论 无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。 推论 无向连通图有欧拉道路，当且仅当中恰有两个奇点。 定理：连通有向图是欧拉图，当且仅当它每个顶点的出次等于入次。,五、中国邮路问题(Chinese postman p

8、roblem),一个邮递员如何选择一条道路，是他能从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程为最短。 给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。 中国邮路问题可用于邮政部门、扫雪车路线、洒水车路线、警车巡逻路线、(计算机绘图)如何节约画笔的空走问题、(计算机制造工业)如何将激光刻制用于集成电路加工的模具等。 定理：已知图G*=G+E1，无奇点，则L(E1)= l(e)最小的充分必要条件为： （1）每条边最多重复一次； （2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。 奇偶点图上作业法。,v5,v6,v9,v8,v7,

9、5,4,3,6,3,4,4,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,第 二 节 树,主要内容： 1.树的概念与性质 2.最小生成树及其算法,1.树连通且不含圈的无向图称为树。树中次为1的点为树叶，次大于1的点称为分枝点。,一、树的概念与性质,2.生成树若图G的生成子图是一棵树，则称该树为G的生成树（或支撑树）。简称为图G的树。图中属于生成树的边叫树枝, 不在生成树的边叫弦。,树枝,树枝,树枝,树枝,树枝,弦,弦,弦,弦,3.最小生成树连通图G=( V，E )，每条边上有非负权L( e )。一棵生成树所有树枝上权的总和称为这棵生成树的权。具有最小权的生成树称为最小生成树（最小支

10、撑树），简称最小树。,定理3 设图G（V，E）是一棵树，n(G)2，则G 中至少有两个悬挂点,（1）T无圈，且m=（n-1）。,定理4 图T=( V，E )，V=n，E=m，若T是一棵树，则下列关于树的说法是等价的。,（2）T连通，且m=（n-1）。 （3）T无圈，但每加一新边即得唯一一个圈。,（4）T连通，但任舍去一边就不连通。 (5 ) T中任意两点，有唯一链相连。,定理5：图G有支撑树的充要条件为G是连通图。,该定理的证明给出了求生成树的方法：每步选出一条边，使它与已经选出的边不形成圈，直至选出（n-1）条边为止。,(1)支撑树的求法:破圈法,（1）避圈法每步从未选的边中选取e，使它与已

11、选边不构成圈，且e是未选边中的最小权边，直到选够（n-1）条边为止。,（2）破圈法每步从未破掉的圈中任选一个圈，将该圈的边中权最大的一条边e去掉，直到图中无圈为止。,例82 一个乡有9个自然村，其间道路及各道路长度如下图所示，各边上的权表示距离，问如何拉电缆线才能使用线总长度最短。,解：这是一个最小生成树问题。具体解法如下：,二、最小生成树的算法,最小树权值为W(T) =5+2+3+2+3+4+6+1=26。,1,2,3,3,4,5,6,2,第 三 节 最 短 路 问 题,一、问题的提出,二、最短路的定义,设D =（V，A）为一个赋权有向图，图中各弧（vi ，vj）有权lij0， vs、vt为

12、图中任意两点，求一条路P0，它是从vs 到 vt的所有路P中总权最小的路。 w(p0) = min w(p),P=(v1 ,v2 , v4 , v5 ),(v1 , v3 , v5 ),P0= (v1 ,v2 , v4 , v5 ),w(p0)=14,三、Dijkstra算法(1959年),用于求解指定两点间的最短路，或从指定点到其余各点的最短路。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等，是目前被认为求无负权网络最短路问题的最好方法。 其采用的是贪心法的算法策略。 Dijkstra算法能得出最短路径的最优解，但由于

13、它遍历计算的节点很多，所以效率低。,1、算法思路,(1) 当lij0时，若从vi 出发的弧中权值最小者是（vi ，vk）那么，从vi至 vk的最短路长必然是lik。,(2)若序列v1， v2， vk， ， vn 是从v1 至 vn 的一个最短路，则序列v1 ， v2 ， vk是从v1至 vk的一个最短路程。即，全局最优，一定是局部最优的。,序列v1， v4，v5 是从v1 至 vn 的一个最短路,则序列v1， v4是从v1 至 v4 的一个最短路,从vs出发，给从vs 到 vk 最短路长的点 vk 赋予固定标号P(permanent label)标号，并记下相应的最短路长（真实的长度）； 而未

14、得到P标号的点，赋予试探性(临时性标号)标号T(tentative label)标号，表示从vs 到vk 点的最短路长的上界。,（3）标记：,P (v1 ) =0,T(v2 )=3,T(v4 )=8,T(v6 )=14,(1)给vs以P标号，P(vs)=0，其余各点均给T类标号， T(vi)=+ (2)若vi点为刚得到P标号的点,考虑这样的点vj： (vi，vj)E,且vj为T标号,对其T标号进行如下更改： T(vj)=min T(vj ) , P (v i)+lij (3)比较所有具有T标号的点,把最小者vk改为P标号： P(vk)=min T(vk) 若vt得到固定标号则停止,否则用vk

15、代替vi,转回(2)。,2、算法的步骤,P(v1)=0,T(v3)=+,T(v2)=+,T(v4)=+,T(v2)=3,T(v3)=1,P(v3)=1,T(v4)=4,T(v2)=2,P(v2)=2,P(v4)=4,(vi)= vm :表示从v1到vi的最短路上, vi的前一个点是vm,(v2)=,v3,(v4)=,v3,S:已获得固定标号的点的集合,例85 用Dijkstra算法求下图中vs 到 vt点的最短路。,3、举例,P(vs)=0,T(v1)=+,T(v3)=+,T(v5)=+,T(v2)=+,T(v4)=+,T(v6)=+,T(vt)=+,T(v1)=4,T(v2)=6,P(v1)

16、=4,T(v3)=9,T(v4)=8,P(v2)=6,P(v4)=8,T(v5)=13,T(v6)=14,P(v3)=9,P(v5)=13,T(vt)=17,P(v6)=14,P(vt)=15,(vt)= v6,T=+,P=0,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=2,T=8,P=2,T=3,P=3,T=4,P=4,T=10,T=11,T=6,P=6,P=8,T=15,P=10,T=14,P=11,P=14,T=15,P=15,P=15,四、带有负权网络的最短路解法 逐次逼近法,（1）基本思想： 若v1 到 vj 的最短路总是沿着该路 从v1 到某一点vi

17、 ，然后再沿着边（ vi ，vj）到 vj 。则从v1 到点vi的这条路，也是从v1 到点vi的最短路。 如果令P1i为从v1 到点vi的最短路长，则下列方程成立： P1j = minP1i +lij i=1, 2, , n 该方程表明： v1到 vj的最短路要依次考察网络中的所有点vi i=1, 2, , n。当改变 vj时，可以求出从v1到其它各个点的最短路。,v4,（2）迭代公式：,P1j(1) =0，3，1， ,P1j(2) =minP1i(1) +lij =minP11(1) +l1j ， P12(1) +l2j ， P13(1) +l3j ， P14(1) +l4j ,P14(2)

18、 =minP1i(1) +li4 =minP11(1) +l14 ， P12(1) +l24 ， P13(1) +l34 ， P14(1) +l44 =min0+ ，3+5，1+3， +0=4,P14(2) =4 , (v4)= v3,P1j(3) =minP1i(2) +lij =minP11(2) +l1j ， P12(2) +l2j ， P13(2) +l3j ， P14(2) +l4j ,P14(3) =minP1i(2) +li4 =minP11(2) +l14 ， P12(2) +l24 ， P13(2) +l34 ， P14(2) +l44 =min0+ ，2+5，1+3， 4+

19、0=4,P14(2) =4 , (v4)= v3,例8-6:求v1到各点的最短路。,第一步：初始条件为： P1j(1) =0，2，5，-3，,第二步：第一次迭代（k=2） P11(2) = minP11(1) ， P12(1) ， P13(1) ，P14(1) ， P15(1) ，P16(1) ， P17(1) ， P18(1) ,+ l11 + l21 + l31 + l41 + l5 1 + l61 + l71 + l81,= min(0+0, 2+, 5+, -3+, , , , ) = 0,P12(2) = minP11(1) ，P12(1) ， P13(1） ，P14(1) ， P1

20、5(1) ，P16(1) ， P17(1) ， P18(1) ,+ l12 + l22 + l32 + l42 + l52 + l62 + l72 + l82,= min (0+2, 2+0, 5+, -3+, , , , ) = 2,V1 V2 V3 V4 V5 V6 V7 V8,i,j,lij,v1 v2 v3 v4 v5 v6 v7 v8,0 ,2 0 ,5 -2 0 4,-3 0 7,4 0 -3 3,6 0 2,0 -1,4 0,P1j(1),P1j(2),P1j(3),P1j(4),P1j(5),0 2 5 -3,0 2 0 -3 6 11,0 2 0 -3 6 6 15,0 2

21、0 -3 3 6 14 10,0 2 0 -3 3 6 9 10,P1j(6),0 2 0 -3 3 6 9 10,最短路径可采取“反向追踪”的方法，依据：,P1j = minP1i +lij i=1, 2, , n,P1j(k) =minP1i(k-1) +lij ,五、求任意两点间最短距离(Floyd algorithm),1、权矩阵：图G=(V，E)，V=n，边（vi， vj)有权lij，则权矩阵 D =(dij)nn被定义为：,2、步骤： （1）输入权矩阵 D（0）=D； （2） D(k) = ( dij (k)nn dij (k) = min(dij (k-1) , dik (k-1

22、) + dkj (k-1) ) (3) k=n，迭代结束， D (n) 中即为任意两点间最短路。,Floyd算法又称插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。,注意： （1）dij (1)表示从vi到vj，借助于v1或不借助于v1到达vj时的 最短路。同理，dij (k)表示从vi 到 vj，借助于k个中间点v1 、 v2 、 、 vk 到达vj的最短路。 由于在第一次迭代时v1已经使用过，第二次迭代只需增加一个新点v2 。依次类推，增加 v3、 v4等等。 （2）当图中不存在负回路(即回路上边的权之和为负数)时，两点间的最短路径最多不超过n步。 （3）如果有无向边，要理解为存

23、在方向相反的两条边。 （4）如果要知道最短路径的信息，则要保留有关下标的信息。,优点：容易理解，可以算出任意两个节点之间的最短距离，稠密图效果最佳，边权可正可负，代码编写简单； 算法描述 a) 初始化：Du,v=Au,v b) For k:=1 to n For i:=1 to n For j:=1 to n If Di,jDi,k+Dk,j Then DI,j:=DI,k+Dk,j; c) 算法结束：D即为所有点对的最短路径矩阵 缺点：时间复杂度比较高O(n3) ，不适合计算大量数据。,例：求图中任意两点间的距离,10,6,7,7,3,7,7,5,4,6,6,6,6,第 四 节 最 大 流

24、问 题,一、问题的提出,3,3,2,1,4,1.网络与流 （1）网络:设有向连通图D=(V，A)，D的每条弧(vi，vj)上有非负数 cij 称为弧的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0 的点 vt 称为收点(汇)，其余点为中间点，这样的网络D称为容量网络，常记为D=(V，A，C)。,二、有关概念,发点,收点,中间点,中间点,(容量),(容量),(容量),(容量),(容量),（1）网络,容量网络,（2）流,对任一D中的弧(vi，vj)有流量fij，称集合f = fij 为网络G上的一个流。,称满足下列两个条件的流 f 为可行流。 容量限制条件： 对D中每条弧(vi，vj)

25、，有0 fij cij,w为网络流的总流量。,对中间点vi ，有,对收、发点vt 、vs ，有,平衡条件,一个流 f = fij ，当 fij= cij，则称流 f 对弧(vi，vj)是饱和的，简称(vi，vj)是饱和弧；当 fij 0，则称弧(vi，vj) 是非零流弧。,饱和弧、零流弧,最大流问题,最大流问题就是求一个流fij使其流量w最大，并且满足容量限制条件和平衡条件。,3.可增广链,若是网络中联结发点和收点的一条链,定义链的方向为从发点到收点,则链上的弧分为两类：一类是弧的方向与链的方向一致,称为前向弧(+ ) ；另一类是弧的方向与链的方向相反(- ) ，称为后向弧。,链=（ v1 ,

26、 v2 , v3 , v4 ）,+=( v1 , v2 ),( v3 , v4 ),-=( v2 , v3 ),可增广链：,设f是一个可行流, 是从vs到vt的一条链,若满足下列条件,称为（关于可行流）的可增广链： 在弧（ vi , vj ） +上，0f ijc ij ，即+中每一条弧是非饱和弧； 在弧（ vi , vj ） -上，0 f ij c ij ，即-中每一条弧是非零流弧,链=（ v1 , v2 , v3 , v4 ）,容量网络D=(V，A，C)，若有弧集A为A的子集，将D分为两个彼此独立的子图D1、 D2，其顶点集合分别为V1、V2， V1 V2=V，V1 V2=，满足： （1）v

27、sV1 ，vtV2 ； （2） D*=(V，A- A)不连通；而A中任一真子集A， D*=(V，A- A)仍连通。则称弧集A为D的截集(割集）。 截集中弧的容量之和称为截集的容量，简称截量，记为C(V1,V2),4、截集、截量、最小截集,A=(v1 ,v2 ), (v3 ,v2 ), (v3 ,v4 ),三、有关理论,定理10 ：设 f 为网络D=(V，A，C)的任一可行流，流量为w，（V1， V2）是D的任一截集， 则有 w C(V1，V2),任一个网络D 中，从vs 到 vt的最大流的流量等于分离vs 、 vt的最小截集的容量。,定理11 (最大流最小截集定理),证明： 设 f *是一个最

28、大流，流量为w，用下面的方法定义点集V1： 令vsV1； 若点vi V1，且 fij0， 则令 vjV1。 反复上面步骤，直到V1无法再扩充为止。 在这种定义下， vt一定不属于V1 。否则，若vtV1，根据V1的定义，可得到从vs到vt的一条链，规定上凡与同向的边称为前向弧，凡与反向称为后向弧。显然，所有前向弧有fij0。我们令,我们把 f *修改为 f1 *：,不难验证 f1 *仍为可行流，但 f1 *的总流量却比 f * 多了，这与 f *是最大流矛盾。故vt不属于V1。,令V2=V- V1，我们有vtV2。于是我们得到一个截集（V1， V2），并且有,但流量又满足,所以，最大流的流量等

29、于最小截集的容量。,容量网络D，若为网络中从vs到vt的一条链，给定向为从vs 到 vt ， 上的边凡与同向称为前向弧，凡与反向称为后向弧，其集合分别用+和-表示，f 是一个可行流，如果满足 ： （1）上的所有前向弧皆是非饱和弧； （2） 上的所有后向弧皆是非零流弧， 则称为从vs到vt 的（关于可行流 f 的）可增广链。,推论 可行流是最大流的充要条件是不存在从vs到vt 的（关于f 的）可增广链。,四、最大流判别,1、首先给定一可行流。 2、然后，开始标号过程。 （1） 给发点vs标号（，+）。其中第一项表示与何点连接，第二项表示可通过的流量。 （2）选择一个已经标号的vi点，对于它的所有

30、未标号邻接点vj按下列规则处理：,五、求最大流标号算法（Ford-Fulkerson),(a) 在弧(vi，vj)上， 如果 fij0，则给vj标号（- vi ， j ）。 j = min i , fji 若vt得不到标号，则不存在可增广链，此时的流为最大流。否则，转向调整过程。 3、调整过程。 如果vt得到了标号，则当前流不是最大流，存在从发点到收点的增广链=+ ， -。,令vt 标号的第二项为，即 t = ，可以 对当前可行流做如下调整：,4、对新的可行流重复标号和调整过程，直至得到最大流。,例:,下图给出一个网络及其初始可行流，每条边上的有序数表示的是（cij，fij），试求这个网络的最

31、大流。,（1）先给vs标号（ ，+）。,(, +),（2）检查这个标号点相邻的顶点v1,v2 ,v3,弧（ vs , v1 ）已经饱和,其它两点满足前向弧流量小于容量的标号条件。,(vs, 1),(vs, 2),(, +),v2 :（ vs, 2）=（ vs ,2）, 2 = min s , cs2- fs2 = 2 v3 :（ vs , 3）=（ vs ,1）, 3 = mins , cs3- fs3=1,先考察与v3相邻的点v6 ，其弧已饱和。所以，转而考察另一个已标号点v2 。根据标号条件， v5 得标号（ v2 ， 5 ）=（ v2 ，2） 。,(v2, 2),(vs, 2),(vs,

32、 1),vt从v5得不到标号,而在(v1 , v5)上,f15 0,所以, v1可以得到标号,由于与行进方向相反,1 = min5 , f15 =2, v1标号为 （- v5 ,1）= （- v5 ，2 ）,(-v5, 2),(v2, 2),(v1, 2),(v4, 2),（3）由于vt得到了标号，所以，当前的流不是最大流，需要调整。在已经找到的增广链上（见图中粉红线）：,（4）调整:前向弧流量加上vt标号第二项的值（2）；反向弧减去第二项的值（2）,(4,4),(3,2),(3,1),(5,4),(4,4),经检查，此时的可行流是最大流，流量为11。,(, +),(vs, 1),例:,下图给

33、出一个网络及其初始可行流，每条边上的有序数表示的是（cij，fij），试求这个网络的最大流。,(, +),(vs, 4),(, +),(-v1, 1),(vs, 4),(v2, 1),(-v2, 1),(-v1, 1),(v3, 1),(5,2),(1,0),(1,0),(2,2),(, +),(vs, 3),w=fs2+fs1=f4t+f3t=5,(8,3),(7,3),(6,5),(5,5),(10,5),(15,15),(6,6),(9,9),(10,2),(11,11),(9,7),(18,7),(7,7),(, +),(vs, 5),(vs, 5),(, +),(v1, 4),(vs

34、, 5),(v4, 1),(v4, 2),(-v4, 4),(v4, 4),(v1, 4),(v4, 1),(-v4, 4),(v4, 4),(v6, 2),(v4, 2),(v8, 2),(v6, 2),(v7, 2),(8, 5),(7, 5),(9, 9),(18, 9),(12, 2),(15, 2),(, +),(vs, 5),(vs, 5),(v4, 1),(v4, 5),(-v4, 5),第五节 最小费用流问题,已知容量网络G=(V,E,C)，每条边(vi,vj)除了已给的容量cij外，还给出了单位流量的费用dij(0)，记G=(V,E,C,d)，求G的一个可行流f=(fij)，

35、使得流量W(f)=v，且总费用最小。 当要求f为最大流时，此问题即为最小费用最大流问题 求解方法：原始算法、对偶算法。,定义：已知网络G=(V,E,C)，f是G上的一个可行流，为从vi 到vj的（关于f的）可增广链， 称为链的费用。,链=（ v1 , v2 , v3 , v4 ）,d()=(4+3)-1=6,-=( v2 , v3 ),+=( v1 , v2 ),( v3 , v4 ),对偶算法的基本思路：,先找一个流量为w( f(0)v的最小费用流，然后寻找从vi 到vj的可增广链，用最大流的方法将f (0)调整到f (1)，使f (1)流量为W(f (0)+，且保证f (1)是在W(f (

36、0)+流量下的最小 费用流，不断进行到W(f (k)=v为止。,第六节 中国邮路问题,一、欧拉回路与道路 定义：连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图（图）。,定理：无向连通图G是欧拉图，当且仅当G中无奇点。,推论 无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。 推论 无向连通图有欧拉道路，当且仅当中恰有两个奇点。 定理：连通有向图是欧拉图，当且仅当它每个顶点的出次等于入次。,二、中国邮路问题,给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，

37、且满足总权最小。 定理：已知图G*=G+E1，无奇点，则L(E1)= l(e)最小的充分必要条件为： （1）每条边最多重复一次； （2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。 奇偶点图上作业法。,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,max z = x1+2x2 +3x3,x1-x2 +x3 -9 3 x1+2x2 -4x3 7 x12x2 + 3x3 -6 x1 0, x2 0, x3 无约束。,1、将下列线性规划化为标准形式,2、写出下列线性规划问题的对偶问题。,3已知四个产地和三个销售地的运输

38、问题，有关数据如下，求最小运费。,4、用单纯形方法求解下面的线性规划问题，并指出有唯一最优解、无穷最优解、无界解还是无解,5、用图解法求解下面的规划问题,max z = 2x1+ 3 x2 +5 x3,x1+ 2 x2 8 4x1 16 4 x2 12 x1 , x2 0,6.给出下列线性规划问题,试分析下列各种条件下最优解（基）的变化 1根据该规划问题的模型与最优单纯形表，求B，B-1，Y 2目标函数中变量x1的系数变为5时，求最优解。 3目标函数中变量x2的系数在何范围变动时，最优解不变 4约束条件右端项由（1 3）T变为（6 3）T时，求最优解5增加一个新的变量x6，P 6=（1 2）T

39、，C6 =5，求最优解,X = (x1 , x2 , x3 )T = (0, 50, 50, )T,9.已知线性规划问题 其对偶问题最优解如下，试求根据对偶理论直接求出原问题最优解。,10、用单纯形法计算某整数规划问题的松弛问题的最终单纯形表如下，用割平面法求出整数规划问题的最优解。,CB,XB,b,x1,x2,x3,x4,x5,x1,x2,x3,11、求解下面的最大化指派问题,12、用分支定界法求解下面的整数规划问题,13、用Dijkstra算法求下图中vs 到 vt点的最短路。 图中数据为各点间的路径长。,14、求下面网络的最大流，图中数据为cij,15、求下面图的最小生成树，图中数据为权值。,