教案图与网络之二

1、运筹学讲课教师：汤建影南京航空航天大学经济与管理学院第四章第四章 网络分析网络分析4.1 网络分析中的常用名词4.2 最小生成树问题4.3 最短路问题4.4 最大流问题4.5 最小费用流问题4.6 中国邮递员问题4.7 网络计划技术第四节 最大流问题n引言n网络流的基本概念n求解网络最大流的基本原理n寻找网络最大流的标号法n确定网络中最大流的方法引言n网络中的流量，称为网络流网络流，如公路系统中的车辆流，控制系统中的信息流，金融系统中的现金流等n设产地与销地之间具有一个交通网，图中每一条弧代表从到的运输线，产品经这条弧由运到，弧旁的数字表示这条运输线的最大通过能力。现要求制定一个运输方案，使从

2、运到的产品数量最多。iv6v1v6v1v1vjvivjv),(jivv1v2v3v4v5v6v1084565331117一、网络流的基本概念n流量与容量n给定一个有向图d=(v,a)，在v中指定一点，称为发点(记为)，同时指定另外一点，称为收点(记为)，其余的点称为中间点。对于每一个弧，对应有一个或简写为，称为弧的容量弧的容量。我们把这样的一个有向图d称为一个网络，记作,容量是弧最大允许流通量n流量流量可看作是某时间内通过弧的物质的数量，记为，是网络流问题中的待求解变量svtvavvji),(0),(jivvcijc),(cavd ijf一、网络流的基本概念n网络流应当满足两个条件n每个弧上的

3、流量不能超过该弧的容量即容量限制条件容量限制条件n中间点的流量为零：平衡条件平衡条件n定义：满足下述条件的流称为可行流可行流n(1)容量限制条件：对每一个弧n(2)平衡条件：对于中间点，对于发点对于收点avvji),(ijijcf 0tsi,0),(),(avvjiavvijijjiffsvtv)(),(),(fvffavvjsavvsjsjjs)(),(),(fvffavvjtavvtjtjjt一、网络流的基本概念n饱和弧与非饱和弧n若给一个可行流，定义网络中（流量等于容量）成立的弧为饱和弧饱和弧，的弧为非饱和弧非饱和弧，的弧为零流弧零流弧，的弧为非零流弧非零流弧n正向弧与反向弧n设是网络中

4、从始点到终点的一条链，凡与链走向一致的弧称为正向弧，逆向的称为反向弧ijff ijijcfijijcf0ijf0ijf一、网络流的基本概念n增广链：对于一可行流 ，网络的一条链上的各弧满足则称该是对于该可行流的增广链增广链n增广链上的正向弧都是非饱和弧，反向弧都是增广链上的正向弧都是非饱和弧，反向弧都是非零流弧非零流弧n沿着增广链可以继续增加流量，增量为沿着增广链可以继续增加流量，增量为ijf),( , 0),( ,jifjicfijijij,minuijuijijffc当有增广链时,找出对对iiiiffcmin再令对非增广链上的弧对所有的对所有的iiiffff显然 仍是一个可行流,与原来的可

5、行流比较发现,网络中从st的流量增大了一个值( 0).f f因此,只有当网络中找不到增广链时,st的流才不可能进一步增大.二、求解网络最大流的基本原理n数学模型ijijaijjiajiijatjjtajttjasjjsajssjcftsifffvfffvfffv0, 0)()()(max),(),(),(),(),(),(所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.二、求解网络最大流的基本原理n给出一初始可行流，例如 。n寻找增广链，若存在，则通过该增广链调整、增加网络流。n若不存在增广链，则网络流不可再增加。求得最大流。n定理：可行流f*为最大流的充分

6、必要条件是当且仅当网络不存在关于f*增广链。0ijf三、寻找网络最大流的标号法n该算法是由ford,fulkerson于1956年提出,故称ford-fulkerson标号法.算法的实质是判断网络中是否存在增广链,并将其找出来.ford-fulkerson标号法首先给发点s标号,记为 ,括号中第一个数字是使这个点得到标号的前一个点的代号,第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值;)(, 0(s找出与已标号点相邻的所有未标号点. 考虑从标号点i出发的弧(i,j),如有不给j点标号;若有 则对j点标号,记为 其中i表示j点的标号是从i点延伸过来的,(正向弧),ijijcf ,

7、ijijcf ),(,(ji;),(min)(ijijfcij 考虑所有指向i的弧(h,i),如有 对h点不标号,若有 则对h点标号,记为 (反向弧), 0hif, 0hif;),(min)(),(,(hifihhi 如果某未标号点k有两个以上的相邻的标号点,为减少迭代次数,可按(1),(2)中的规则,分别计算 的值,取其中最大的一个标记.)(k 重复步骤2,可能出现两种结局: 标号过程中断,t点得不到标号,说明网络中不存在增广链,网络中给定的流就是最大流.计算结束; t点得到标号,这时反向追踪,在网络中找到一条从s到t 的由标号点和相应的弧连结而成的增广链. 修改流量:设在网络中原有的流量为

8、f.;)()(fftftff新可行流于是的到网络上的一个对非增广链上的弧弧对增广链上的所有后向弧对增广链上的所有前向令 抹去网络图中的所有标号,重复第1到第4步,一直到在网络中找不到任何增广链,即出现第3步的结局(1)为止,这时网络中的流量为网络的最大流.ford-fulkerson标号法(小节)nford-fulkerson标号算法，给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链。否则不存在增广链。n调整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流v(f)增加一个调整量：)()(fvfv例4-2：第一次迭代第二次

9、迭代第三次迭代：最优解四、确定网络中最大流的方法n最大流时始节点的净流出量n最大流时中介点的净流入量n最小割集的容量n割集n割集容量n最小割集n最小割集最大流定理n标号法求得最小割集在下图中,括弧外的数字表示最大通过量,括弧內的数字为负载.st1v2v3v4v)8(8)5(7)4(5)4(9)0(2)9(9) 1 (6)5(5)8(10割集:将网络流中的发点和收点分割开,使s到t的流中断的一个弧集合.kk.),(),(),(,4231vvvvvvvtvskk弧集合割如 割量:割的弧集合中各弧的容量之和,用表示,显然,),(vvc).,(,),(),(vvjivvcvvcji 割割的容量 15

10、21 17 18 19 24 14 25 25vvstvvvv,4321)2 ,(),1 ,(ss1, vstvvv,432)3 , 1 (),2 , 1 (),2 ,(s2, vstvvv,431)4 , 2(),1 ,(s21,vvstvv,43)4 , 2(),3 , 1 (31,vvstvv,42), 3(),2 , 3(),2 , 1 (),2 ,(ts42,vvstvv,31), 4(),3 , 4(),1 ,(ts321,vvvstv ,4), 3(),4 , 2(t421,vvvstv ,3), 4(),1 , 4(),3 , 1 (t4321,vvvvst), 4(), 3(

11、tt.:).,(14).,(),(),()(),(),()(,)().,(),()(,),(),(),(),(,),(),(;),(),(*割集的容量的最大流等于它的最小在网络中定理集称为最小割其中割的容量最小的割割的容量不同最大流不超过的在本例中根据割的概念则的最大流表示网络中从若用即量总和的流的流量总和减去从的流量等于割中从从则有方向弧的流量总和中所有表示割用方向弧的流量总和中所有表示割用tstsvvcvvfvvffvvvfvvffvtsfvvvfvvffvvvvvtsvvfvvfvvfvvfvvvvvvfvvvvvvfijji一个简单的例子st1v2v3v4v)8(8)5(7)4(5)4

12、(9)0(2)9(9) 1 (6)5(5)8(10例8 用标号法求下面网络从s到t的最大流量,并找出该网络的最小割.), 0()2 ,(s)2 ,(2v)2 ,(1v) 1 ,(3v) 1 ,(4v解:先给s标号 ;), 0(从s点出发的弧为 ,因为对 暂时不标号,而),(),(21vsvs811sscf1v);2 ,(, 257 ,min)(),(min)(),(,(22222svfcsvvsss标号对其中标号对222,75vcfss);2 ,(, 24 , 2min),(min)(),(,(, 0),(, 9),(),(, 0),(),(21122112112212424422332232

13、12vvfvvvvvfvvcfvvvvfvvvvv号为的标其中标号故对对反向弧不考虑此弧对于弧不考虑弧的弧有指向);2 ,(, 25 , 2min)(),(min)(),(,(,94),(131313133131313211vvfcvvvvvcfvvv的标号为其中标号对因为出发的弧为从已标号点 );1 ,(, 11 , 2min),(min)(),(,(, 0),(?)(,(),(34433443443343233vvfvvvvvfvvtvvvv的表号为其中标号故对因为对于反向弧为什么显然不考虑弧对已标号点 );1 ,(, 12 , 1min810, 1min),(min)(),(,(,),(

14、44444444vtfcvttvtcftvtttt标号对其中点得到标号因为是从已标号点出发的弧对于弧因为t点得到标号,用反向追踪法可找出从s到t的一条增广链,用红线标出;修改增广链上的流量:其余弧上的流量不变,于是得到网络上的一个新可行流,重复上述的标号过程,转下一步;前向弧后向弧前向弧后向弧前向弧918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttssst1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10), 0() 1 ,(s) 1 ,(2v) 1 ,(1v) 1 ,(3v) 1 ,(4

15、v标号中断,t点得不到标号,网络中没有增广链,该网络的可行流就是最大流,最大流量为)(14)(*收点的总输入量发点的总输出量 fv);, 0()9(标号对s);1 ,()67 ,min,(,76),(),()10(22221ssvcfvsvsss标号对因为而考虑弧不考虑弧 );1 ,()3 , 1min,(),(min,(),(),(),(,)11(22122212123422vvfvvvvvvvvvv标号对考虑反向弧只不考虑弧出发从已标号点 );1 ,()4 , 1min,(),(min,(,),()12(1113131131313311vvfcvvvcfvvv标号故对因为出发的弧考虑从已标

16、号点.14)(,),(),()13(*343fvttvvv最大流是中的可行流最大流就是网络网络中不存在增广链得不到标号点因此标号中断均不能考虑弧下面求该网络的最小割:.1495,)4 , 2(), 3(),(.)(,表示最小割的位置线画出小割的容量的结论了最大流的流量等于最印证最小割的容量为该网络的最小割为称为最小割后向弧不包含的弧集合及则连接标号点的集合记为未已标号点的集合记为在产生最大流的网络中kktvvvvvvst1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10), 0() 1 ,(s) 1 ,(2v) 1 ,(1v) 1 ,(3v) 1 ,(4

17、vkk习题np.266，习题4，图9-5（1）、（2）。第六节 中国邮递员问题n哥尼斯堡七桥问题与欧拉图n中国邮递员问题n求解中国邮递员问题的奇偶点图作业法n奇偶点图作业法的改进方法一、哥尼斯堡七桥问题与欧拉图n哥尼斯堡七桥问题n欧拉图与一笔画问题二、中国邮递员问题n1962年，管梅谷先生提出中国邮递员问题n若图中无奇点，欧拉圈即为所求n若图中有奇点，则奇点必为偶数，在奇点间加边（重复走），使其变为偶数而成欧拉图。n中国邮递员问题是要求所加边的权之和最小。三、求解中国邮递员问题的奇偶点图作业法n基本思想：n把一个有奇点的图增加重复边后成为不含奇点的欧拉图，构造初始可行方案；n寻找是否存在使重复边路长减少的改进的可行方案。奇偶点图作业法步骤n构造初始可行方案：由于奇点个数必为偶数，因此奇点必成对出现；同时由于图是连通的，因此每一对奇点之间必存在一条链，在这条链上