网络最大流问题.pptx

《网络最大流问题.pptx》由会员分享，可在线阅读，更多相关《网络最大流问题.pptx（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第六章 图与网络分析第一节 图的基本知识第二节 树第三节 最短路问题第四节 网络最大流问题第五节 最小费用最大流问题 第1页/共52页第四节 网络最大流问题8431763511v1v2v3v5v4v6105图10-23是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。现在要求制定一个运输方案使从v1运到v6的产品数量最多。图10-23第2页/共52页v1v2v3v5v4v6图10-2410-24给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案使8 8个单位的产品从v

2、v1 1运到v v6 6。在这个运输网络中，从v v1 1到v v6 6的最大输送量是多少呢?8431763511v1v2v3v5v4v6105图10-23图10-24第3页/共52页一、一、基本概念与基本定理1、网络与流 定义1 给一个有向图D=(V,A)，在V中指定了一点，称为发点(记为vs)，和另一点，称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)A,对应有一个c(vi，vj)0(或简写为cij)，称为弧的容量。通常把这样的D叫作一个网络。记作D=(V，A，C)。对D中的任一弧(vi，vj)有流量f(vi，vj)(有时也简记作fij)，称集合f=fij为网络D上的一个

3、流。第4页/共52页2 2、可行流与最大流定义2 满足下述条件的流 f 称为可行流：1）容量限制条件：对每一弧(vi，vj)A0fijcij可行流2 2）平衡条件：对于中间点：流出量流入量，即对每个i(is,t)i(is,t)有第5页/共52页对于发点v vs s，式中v v(f)(f)称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。于是对于收点v vt t，或第6页/共52页 所谓最大流问题就是在网络中，寻找流量最大的可行流，即：求一个流ffijij 使其流量v(f)v(f)达到最大，并且满足0 0f fijijc cijij (v (vi i，v vj j)A)A最大流 可行流

4、总是存在的，例如(f fijij)=0就是一个流量为0的可行流。第7页/共52页3 3、增广链 若给一个可行流f=fij，我们把网络中使 fij=cij 的弧称为饱和弧，使fij0的弧称为非零流弧。若是网络中联结发点v vs s和收点v vt t的一条链，我们定义链的方向是从v vs s到v vt t，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫作前向弧。前向弧的全体记为+。另一类弧与链的方向相反，称为后向弧。后向弧的全体记为-。第8页/共52页 定义3 设f是一个可行流，是从vs到vt的一条链，若满足下列条件,称之为(关于可行流 f 的)一条增广链。在弧(vi，vj)+上，0fij

5、cij，即+中每一弧是非饱和弧。在弧(vi，vj)-上，0fijcij，即-中每一弧是非零流弧。图10-24中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因为+和-中的弧满足增广链的条件。如：(v1,v2)+,f12=50。第9页/共52页4 4、截集与截量 设S,TVS,TV，ST=ST=，我们把始点在S S，终点在T T中的所有弧构成的集合，记为(S(S，T)T)。定义4 4 给网络D=(VD=(V，A A，C)C)，若点集V V被剖分为两个非空集合V V1 1和 ，使v vs sVV1 1，v vt t ，则把弧集(V(V1 1,),)称为是(分离v vs s和v vt t

6、的)截集。可以看出，从网络中去掉任一截集，则从v vs s到v vt t便不存在路。所以，截集是从v vs s到的v vt t必经之路。第10页/共52页定义5 5 给一截集(V(V1 1,),)，把截集(V(V1 1,),)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(Vc(V1 1,),)，即 任何一个可行流的流量v v(f)(f)都不会超过任一截集的容量。即第11页/共52页 显然，若对于一个可行流f*，网络中有一个截集(V1*,)，使v(f*)=c(V1*,),则f*必是最大流，而(V1*,)必定是D的所有截集中容量最小的一个，即最小截集。第12页/共52页定理1 可行流

7、f*是最大流的充分必要条件是不存在从v vs s到v vt t的(关于f*)增广链。证明：(一)必要性 用反证法。可行流f*是最大流，假设存在从v vs s到的v vt t的(关于f*)增广链。令：第13页/共52页由增广链的定义，可知0,令网络上的另一个流：仍为可行流(即满足容量限制条件与平衡条件)，但 的总流量等于 的流量加，即这与 是最大流的前提矛盾。第14页/共52页 (二)充分性：若不存在关于f*增广链，那么f*是最大流。因为不存在关于f*增广链，那么在这种定义下，。令：则 。因此，可以得到一个截集 。令：若且则令 若且则令 用下面方法定义点集 第15页/共52页显然有那么，可行流f

8、*上的流量则f*必然是最大流。第16页/共52页 最大流量最小截量定理：任一个网络D D中，从v vs s到v vt t的最大流的流量等于分离v vs s，v vt t的最小截集的容量。增广链的实际意义是：沿着这条链从v vs s到v vt t输送的流，还有潜力可挖，只需按照定理1 1证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广链时就得到了最大流。第17页

9、/共52页寻求最大流的思路：利用定理1中对V1*定义，根据vt是否属于V1*来判断D中有无关于f的增广链。实际计算时，可以用给顶点标号的方法来确定属于V1*的点。在标号过程中，有标号的顶点表示是V1*中的点，没有标号的点表示不是V1*中的点。一旦vt有了标号，就表明找到一条增广链；如果标号过程进行不下去，而vt尚未标号，则说明不存在增广链，于是得到最大流。而且同时也得到一个最小截集。第18页/共52页二、二、寻求最大流的标号法 设已有一个可行流(若网络中没有给定f，则可以设f是零流)，从这个可行流开始，标号法的过程分为两步：第一步：标号过程，通过标号来寻找增广链；第二步：调整过程，沿增广链调整

10、 f 以增加流量。第19页/共52页 在标号过程中，网络中的点分为两类：(1)标号点(又分为已检查和未检查两种)。每个标号点的标号内容包含两部分：标号的第一部分表明它的标号是从哪一点得到的，以便找出增广链；标号的第二部分是为确定增广链的调整量用的。(2)未标号点。1 1、标号过程 第20页/共52页标号过程:(1)给发点vs标上(0，+)；这时vs是标号而未检查的点，其余都是未标号点。(2)取一个标号而未检查的点vi，对于vi的所有未给标号的相邻点vj按下列规则处理：(a)若若在在弧弧(vi,vj)上上，fij0，则则给给vj标标号号(-vi，l(vj)，这这里里l(vj)=min(l(vi)

11、,fij。这时点。这时点vj成为标号而未检查的点。成为标号而未检查的点。这样，这样，v vj j成为标号而已检查过的点。成为标号而已检查过的点。第21页/共52页 若若vt未未获获得得标标号号，而而标标号号过过程程无无法法进进行行时时，则则算算法法结结束，这时的可行流束，这时的可行流 f 就是最大流。就是最大流。(3)重复步骤(2)，直到vt被标上号，表明得到一条从vs到vt的增广链，转入调整过程。第22页/共52页 例如：设vt的第一个标号为vk，则弧(vk,vt)是上的弧。接下来检查vk的第一个标号，若为vi，则找出(vi,vk)。再检查vi的第一个标号，依此下去，直到vs为止。这时被找出

12、的弧就构成了增广链。1 1、调整过程 (1)找出增广链。按vt及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。第23页/共52页 (2)在增广链上调整流量。令调整量为 l(vt)，即vt的第二个标号。(3)去掉所有的标号，对新的可行流 ，重新进入标号过程。第24页/共52页例例 用用标标号号法法求求图图10-25所所示示网网络络的的最最大大流流。弧弧旁旁的的数是数是(cij,fij)。解 (一)标号过程 (1)首先给vs标上(0，+)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)图10-25第25页/共52

13、页(2)检查检查vs。vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)弧弧(vs，v1)上上，fs11，cs1=5，fs10，则则给给v2记记下下标标号号为为(-v1,l(v2)，这里，这里 l(v2)=minl(v2),f21=min4，1=1 在弧在弧(v1，v3)上，上，f13=2，c13=2，不满足标号条件。，不满足标号条件。第27页/共52页(4)检查检查v2。vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(

14、-v1,1)(v2,1)(-v2,1)在在弧弧(v2，v4)上上，f21=3，c24=4，f240，给，给v3标号：标号：(-v2,l(v3)，l(v3)=minl(v2),f32=min1,1=1第28页/共52页(5)在在v3,v4中任选一个进行检查中任选一个进行检查。(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)例例如如，在在弧弧(v4，vt)上上，f4t=3，c4t=5，f4t c4t,给给vt标标号为号为(v4,l(vt)，这里，这里l(vt)

15、minl(v4),(c4t-f4t)=min1,2=1因因vt有了标号，故转入调整过程。有了标号，故转入调整过程。第29页/共52页(二)调整过程 (v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)(1)按点的第一个标号找到一条增广链。第30页/共52页(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)(2)在增广链上调整

16、流量。在增广链上 +=(vs，v1),(v2，v4),(v4，vt)-=(v2，v1)第31页/共52页(v4,1)vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)(0,+)(vs,4)(-v1,1)(v2,1)(-v2,1)按=1在上调整f。+上：-上：第32页/共52页vsv2v1v3vt(3,3)(5,1)(4,3)v4(2,2)(1,1)(1,1)(3,0)(5,3)(2,1)vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)调整后的网络图如下:第33页/共

17、52页vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)对新的可行流再进入标号过程，寻找增广链(一)标号过程 (1)首先给vs标上(0，+)第34页/共52页vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)(2)检查检查vs。(vs,3)弧弧(vs，v1)上上，fs12，cs1=5，fs1 cs1,则则v1的的标标号号为为(vs,l(v1)，其中，其中，l(v1)=minl(vs),(cs1-fs1)=min+,5-3=3 在弧在弧(vs，v2)

18、上，上，fs2=cs23，不满足标号条件。，不满足标号条件。第35页/共52页vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)(vs,3)(3)检查检查v1。标号过程无法继续下去，算法结束。标号过程无法继续下去，算法结束。在弧在弧(v2，v1)上，上，f21=0，不满足标号条件。，不满足标号条件。在弧在弧(v1，v3)上，上，f13=2，c13=2，不满足标号条件。，不满足标号条件。第36页/共52页这时的可行流即为所求最大流。最大流量为：v(f)=fs1+fs2=f4t+f3t5。vsv2v1v3vt(3,3)(5,

19、2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)第37页/共52页vsv2v1v3vt(3,3)(5,2)(4,4)v4(2,2)(1,0)(1,1)(3,0)(5,4)(2,1)(0,+)V1 同时，可以得到已标号点集合V1=vs,v1，和未标号点集合 =v2,v3,v4,vt。相应地，弧集合 =(vs,v2),(v1,v3)即为最小截集，它的容量也是5，等于最大流量。第38页/共52页 由此，也可以体会到最小截集的意义。网络从发点到收点的各通路中，向容量决定其通过能力，最小截集则是这些路中的咽喉部分，或者叫瓶颈，其容量最小，它决定了整个网络的最大通过

20、能力。要提高整个网络的运输能力，必须首先改进这个咽喉部分的通过能力。第39页/共52页第40页/共52页8431763511v1v2v3v5v4v6105图10-23 例如，图10-23就是一个网络，指定v1是发点，v6是收点，其它的点是中间点。弧旁的数字为cij。第41页/共52页v1v2v3v5v4v6 图10-24所示的运输方案，就可看作是这个网络上的一个流，每个弧上的运输量就是该弧上的流量，如：f12=5，f24=2，f13=3，f34=1。图10-24第42页/共52页v1v2v3v5v4v6图10-2410-24给出了一个运输方案，每条弧旁的数字表示每条运输线上的运输数量。这个方案

21、使8 8个单位的产品从v v1 1运到v v6 6。在这个运输网络中，从v v1 1到v v6 6的最大输送量是多少呢?8431763511v1v2v3v5v4v6105图10-23图10-24第43页/共52页v1v2v3v5v4v6 图10-24中，(v5,v4)是饱和弧，其它的弧为非饱和弧。所有弧都是非零流弧。图10-23图10-248431763511v1v2v3v5v4v6105第44页/共52页8431763511v1v2v3v5v4v6105图10-23 图10-23中，在链=(v1,v2,v3,v4,v5,v6)中 +=(v1,v2),(v2,v3),(v3,v4),(v5,v

22、6)-=(v5,v4)第45页/共52页v1v2v3v5v4v6 图10-24中，链=(v1,v2,v3,v4,v5,v6)是一条增广链。因为+和-中的弧满足增广链的条件。比如：(v1,v2)+,f12=50。图10-248431763511v1v2v3v5v4v6105图10-23+1+1+1-1+1第46页/共52页8431763511v1v2v3v5v4v6105图10-23 例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)、弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络D的截集。弧集(v4,v6)，(v2,v5)，(v3,v5)也是网

23、络D的截集。8431763511v1v2v3v5v4v6105第47页/共52页8431763511v1v2v3v5v4v6105图10-23 例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)、弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络D的截集。弧集(v4,v6)，(v2,v5)，(v3,v5)也是网络D的截集。8431763511v1v2v3v5v4v6105第48页/共52页由增广链的定义，可知0,令网络上的另一个流：仍为可行流(即满足容量限制条件与平衡条件)，但 的总流量等于 的流量加，即这与 是最大流的前提矛盾。第49页/共52页8431763511v1v3v2v4v5v6105图10-23 例如，弧集(v1,v2)，(v2,v3)，(v2,v5)，(v2,v4)和弧集(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)都是网络D的截集。第50页/共52页第51页/共52页感谢您的观看！第52页/共52页