6_网络最大流

1、第第1页页第六章第六章网络最大流网络最大流第第2页页网络最大流问题网络最大流问题50年代福特（年代福特（Ford）、富克逊（）、富克逊（Fulkerson）建立）建立的的“网络流理论网络流理论”，是网络应用的重要组成部分。，是网络应用的重要组成部分。如同我们可以把一个实际的道路地图抽象成一个如同我们可以把一个实际的道路地图抽象成一个有向有向图图来计算两点之间的来计算两点之间的最短路径最短路径，我们也可以将一个，我们也可以将一个有向图有向图看作一个看作一个流网络流网络来解决另一类型的问题。来解决另一类型的问题。流网络比较适合用来流网络比较适合用来模拟液体流经管道模拟液体流经管道、电流电流在电路在

2、电路网络中的运动、网络中的运动、信息信息网络中信息的传递等等类似的过程。网络中信息的传递等等类似的过程。第第3页页问题的提出问题的提出 在一个在一个输油管网输油管网中，有生产石油的中，有生产石油的油井油井、储存石油的、储存石油的油油库库、转运石油的中间、转运石油的中间泵站泵站，同时，还有各种口径不同的，同时，还有各种口径不同的输油输油管管。当一个输油管网给定后，单位时间内最多可把多少石油。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？从油井输送到油库？具体方案如何？ 分析：分析：就输油管网络问题，可用就输油管网络问题，可用顶点顶点表示油井、油表示油井、油库和中

3、间泵站，用库和中间泵站，用有向边有向边表示输油管，用有向边上表示输油管，用有向边上的的权权表示单位时间沿相应的输油管可以输送石油的表示单位时间沿相应的输油管可以输送石油的最大数量（最大数量（容量容量）。）。 第第4页页如果我们把图看做输油管道网，如果我们把图看做输油管道网， 为起点，为起点， 为终点，为终点， 为中转站，为中转站，边上的数表示该管道的最边上的数表示该管道的最 大输油能力大输油能力，问应该如何安排各管道输油量，才能，问应该如何安排各管道输油量，才能 使从使从 到到 的的总输油量最大总输油量最大？ tvsv1234,v v v vtvsv问题的提出问题的提出管道网络中每边的最大通过

4、能力即管道网络中每边的最大通过能力即容量容量是有限的，实际是有限的，实际流流量量也不一定等于容量，上述问题就是要讨论如何充分利用也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通装置的能力，以取得最好效果（流量最大），这类问题通常称为常称为最大流问题最大流问题。vsv1v3vtv2v48799562510第第5页页容量容量发点（源）发点（源）收点（汇）收点（汇）中间点中间点容量网络容量网络( ,)ijDv v的每条弧上有非负数的点的点一个入次为一个入次为0sv的点的点一个出次为一个出次为0tv其余点其余点( , ,)DV A Cijc网络有向图网

5、络有向图D=D=（V V，A A，C C） 网络上流的基本概念网络上流的基本概念vsv1v3vtv2v48799562510流流( ,)ijijv vf对D中任一弧都给定一个实际流量ijff 集合集合(1)(2)满足下面条件的流：容量限制条件中间点平衡条件ijijcf 0 jijkkiff输出量输出量中间点的输入量中间点的输入量 ( )( )sjjtjjv fstv fff用表示网络中从的流量 vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)00f 任何网络必存在可行流，如流量为 的可行流：运输问题中，每个运运输问题中，每个运输方案就是一个流输

6、方案就是一个流可行流可行流第第7页页 ( )ijfv f在容量网络中，寻求一个流使其流量最大网络最大流问题网络最大流问题ijijcf 0( )0( )ijjiv fffv f( , )tjv vA()is(, )is t()i t且满足此为一个此为一个特殊的线性规划问题特殊的线性规划问题，将会看到利用图的特点，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。解决这个问题的方法要比单纯形法较为直观方便。第第8页页设设 是是网络网络D=D=（V V，A A，C C）的）的一个可行流一个可行流（v1，v2）是饱和的是饱和的2、如果、如果0fij0，该弧是该弧是非非0弧弧；（v1，v

7、2）是非是非0弧弧3、如果、如果fijij= =0，该弧是，该弧是0 0流弧流弧；弧关于流的分类弧关于流的分类ijffv1v2v1v2第第10页页链及可增广链链及可增广链链链在最大流问题中，研究的是有向网络图。但是在求最大流在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。的方法中，则要使用无向网络中的链。,ststvvvvD中，若 为从 到 的一条链，给 定向为从 到前向弧集：与 同向 后向弧集：与 反向，vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)( ,)( ,)ijijijijijfv vffv vf

8、非增广链上的弧(,)(,)min0ijijijijijijijcfv vfv v()( )v fv f11fc30f 22fc0( ,)0( ,)ijijijijijijstffcv vfcv vfvv 是可行流，每一个若每一个则称 为关于可行流 的从 到 的可增广链。非非0流弧流弧可增广链可增广链10nfnnfcvsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非饱和弧非饱和弧第第12页页11VV割集和割集的容量割集和割集的容量)(111VVVV和11,VvVvts1V1V),(11VV 设有网络设有网络D=VD=V，A A，CC，点，点v v

9、s s与点与点v vt t的是集合的是集合V V中的任意两中的任意两点，若点集点，若点集V V被剖分成两个非空集合被剖分成两个非空集合 ，使，使，记以，记以中的点为中的点为始点始点，的的A A中弧的集合记为中弧的集合记为则称这个弧的集合则称这个弧的集合是分离点是分离点v vs s与点与点v vt t的的割集割集（又称截集）。（又称截集）。中的点为中的点为终点终点割集的容量割集的容量是割集中各弧的容量之和，用是割集中各弧的容量之和，用 表示。表示。11( ,)c V V1324( ,),(,)v vv v112134 , , tVs v vVv v v割集的容量为割集的容量为9+9=189+9=

10、18割集割集KKvsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考虑考虑KK的不同画法的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)1234,v v v v t34(, ),(, )v tvt12( ,),( ,)s vs v1 , s v s2 ,s v12 ,s v v13 ,s v v24 ,s v v123 ,s v v v124 ,s v v v1234 ,s v v v v234,v v v t134,v v v t134,v v v t24,v v t13,v v t1

11、234,v v v v t4,v t t21213( ,),(,),(,)s vv vv v124( ,),(,)s vvv1324(,),(,)v vvv212323( ,),(,),(,),(, )s vv vvvv t1434( ,),(,),(, )s vvvvt243(,),(, )vvv t13434( ,),(,),(, )v vvvvt152117181924142515VV割集割集割集容量割集容量第第14页页111111( , ,),( ),( ,),( ,)( )( ,)ststfDV A CvvW fV Vv vV VW fC V V设 为网络的任一可行流( 为发点为收点

12、），流量为是分离的任一割集，割集容量为C则有基本定理基本定理(可行流与割集的关系可行流与割集的关系)由于有限网络的割集只有有限多个，则截集容量的集由于有限网络的割集只有有限多个，则截集容量的集合合是有限的实数集合，令是有限的实数集合，令 称割集容量为称割集容量为C0 0的割集为的割集为D D的最小割集。（的最小割集。（瓶颈瓶颈）11(,)C V V011 ( ,)Cmin C V V第第15页页wffSjSijiij ,又 0fijcij fijfjifijcij因为割集是任意的，所以得证。SjSiijSjSijiijcffw,C(S, ) S第第16页页的可增广链到不存在从是最大流可行流ts

13、vvf增广路定理：增广路定理：证明：1 必要性 v(f)为最大流，则不存在可增广链； 因为若存在增广链，则v(f)不为最大流。2 充分性 不存在可增广链，则v(f)为最大流； 若网络流图G中不存在可增广路，则考察所有s到t的路 径，将满足增广条件路径连接的节点并入集合S中，遇 到不满足条件点时停止；T=V/S，S,T为s-t割集。 这时，对于任意弧(i,j)，若是前向弧，fij=cij，若是逆 向弧，fji=0,下式成立，v(f)为最大流,CS,T为最小割。 =TjSiijTjSijiijcffw,C(S, ) T第第17页页最大流最大流-最小割定理：最小割定理：的的最最小小割割的的容容量量分

14、分离离的的最最大大流流的的流流量量到到从从中中，任任一一个个网网络络tstsvvvvG, v(fmax)=CminS,T;第第18页页这样就得到了一个这样就得到了一个寻求最大流的方法寻求最大流的方法(算法思想算法思想)：从一个从一个可行流可行流开始，寻求关于这个可行流的开始，寻求关于这个可行流的可增可增广链广链，若存在，则可以经过调整，得到一个新的，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时过程，直到不存在关于该流的可增广链时就得到了最大流。就得到了最大流。沿着这条链从沿着这条链从

15、 vs 到到 vt 输送流，还有潜力可挖，输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。即仍为可行流。可增广链可增广链的实际意义的实际意义求解最大流的标号算法：求解最大流的标号算法：Ford-Fulkerson1.()1( ,)2,:( ),min,(,)( )0,min,(,)(3)(2siijjiijijjijijiijjijijjiiijvvvvavvfccfvbvvffv 标号过程 寻找可增广链 ：（ ）给 以标号（ ）对已标号的

16、考虑 的所有未标号的邻接点若是 发出的前向非饱和弧的终点， 即令标号为；否则不标号对是 发出的后向非零弧的起点， 即令标号为；否则不标号重复)2.121tstijtijijtijvvvfffff直到 若 未得到标号，说明不存在 到 的增广链； 否则按如下方法调整。调整过程（增加流量）：增广链上的前向弧（ ）令增广链上的后向弧不在增广链上（ ）去掉所有标号，回到第 步，对可行流重新标号。()( )tw fw f则有1v2v3vb)b) 接着检查与相邻接的点接着检查与相邻接的点1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3

17、, 3()3 , 3()0 , 3()2 , 2()2 , 2(),( 已饱和，流量不可再增。再检查已饱和，流量不可再增。再检查 ，可调整量为，可调整量为 4-2=2，可提供量可提供量+，取调整量，取调整量1v2v2min42,2 先给标号先给标号 （，+）1） 寻找可增广链：寻找可增广链：sv1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),( 3v) 1,(sv 下对已标号点（可望调整点）接着向下检查。下对已标号点（可望调整点）接着向下检查。 已饱已饱

18、 和。再检查与和。再检查与 相邻接且未标号的点相邻接且未标号的点 6v2v,5v6v给给 标号标号 ，其中，其中 表示表示 的所调整量的所调整量2来自来自 ，且为正向流（向前流）且为正向流（向前流） 。)2 ,(svsv2vsv2v)2 ,(sv) 1 ,(sv调整量为调整量为1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv5min30, 22)2 ,(2v5v给给 标号为标号为)2 ,(2v1v3v2v4v5vsvtv6

19、v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v可令调整量为可令调整量为1min3, 22)2 ,(5v给给 标号为标号为)2 ,(5v1v表示可控量，反方向流量表示可控量，反方向流量。5v, 015 fd) 检查与检查与 相邻接且未标号的点相邻接且未标号的点 ， 。而。而 对对 来讲是来讲是流流 入，现欲增加流出量，应该压缩入，现欲增加流出量，应该压缩 的流入量，只要的流的流入量，只要的流入量入量1vtv1v5v1v1v3v2v4v5v

20、svtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5vf) 下面检查与下面检查与 相邻接且未标号的点相邻接且未标号的点 ，同理，调整量：，同理，调整量：1v4v4min52, 22给给 标号为标号为).2 ,(1v4v)2 ,(1v)2 ,(4vg) 最后，给最后，给 标号标号tv).2 ,(4vmin42, 22t1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4

21、 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v2）调整流量：从）调整流量：从 到到 所画出的所画出的红线红线即为即为可增广链可增广链。沿。沿该可增广链，从该可增广链，从 倒推，标倒推，标“”号的在实际流量上加上号的在实际流量上加上该调整量，标该调整量，标“”符号的在实际流量上减去该调整量。符号的在实际流量上减去该调整量。完完成调整过程。成调整过程。svtvtv反反向向追追踪踪1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 ,

22、 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 , 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 , 4()4 , 5()4 , 4()4 , 5()3 , 3() 1

23、, 3()2 , 3()2 , 2()2 , 2(),() 1 ,(sv当标到当标到 时，与时，与 ， 相邻接的点相邻接的点 ， ， 都不满足标都不满足标号条件，标号无法继续，且号条件，标号无法继续，且 没有完成标号。此时最大流量没有完成标号。此时最大流量即为所求。即为所求。) 1 ,(svsv3v1v2v6vtv*12354211ssswfff312456 ,; ,;stVv vVv v v v v v标号点集未标号集12361236( , )( ,),( ,),( ,)( , )11ssssV Vv vv vv vC V Vccc割集割集容量重新开始标号，寻找可增广链。重新开始标号，寻找可

24、增广链。第第28页页课堂练习求下图所示的网络流图的最大流。sabt120202020第第29页页若标号次序出现特殊情况，如下图所示：sabt(1,0)(20,0)(20,0)(20,0)(20,0)(,)(+b,1)(+s,20)(+a,1)出现增流路径如图所示，增流1(20,0)(1,0)(20,0)第第30页页若标号次序出现特殊情况，如下图所示：sabt(1,1)(20,1)(20,1)(20,0)(20,0)(,)(+a,1)(+s,20)(-b,1)出现增流路径如图所示，增流1(20,0)(1,1)(20,0)第第31页页 上述两条增流路径如此交替出现，需要进行220次才能求出最大流。

25、sabt(1,1)(20,2)(20,2)(20,1)(20,1)( ,)(-b,1)(+s,19)(+a,1)sabt(1,0)(20,1)(20,1)(20,1)(20,1)(,)(+s,19)(+a,1)(+b,1)第第32页页Edmonds-Karp修正算法 Edmonds-Karp算法描述：（1）初始流v(f)=0；（2）给源点s标号(,)，其它顶点均未标号；（3）按层次依次对可以标号的顶点进行标号，若当）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为前标号的顶点为t，调整流，调整流，转（转（2）；）；（4）这时得到的f就是最大容许流。第第33页页用Edmonds-Karp算

26、法求下图的最大流sabct95724386第第34页页算法从流量0开始；查找可增广链，若不存在，算法结束，此时流量就是最大的；若不存在，通路增加流量，重复 2。输入：网络G，容量C，a, z, n；输出：最大流量F；Procedure max_flow(a,z,C,v,n)/ v的标记为的标记为 (predecessor(v)/前趋结点，前趋结点，val(v)/结结点点v的流量增量的流量增量第第35页页第第36页页/没有新的通路没有新的通路第第37页页/正向边正向边第第38页页/反向边反向边第第39页页第第40页页/增量增量第第41页页网络从发点到收点的各通路中，由容量决网络从发点到收点的各通

27、路中，由容量决定其通过能力，定其通过能力，最小割最小割则是这此路中的则是这此路中的咽喉部咽喉部分分，或者叫，或者叫瓶颈瓶颈，其容量最小，它决定了整个，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部份的通过能力。能力，必须首先改造这个咽喉部份的通过能力。最小割的意义最小割的意义第第42页页下图看做输油管道网，下图看做输油管道网，最大输油能力为多少最大输油能力为多少，问应，问应该如何安排各管道输油量，如何增加该如何安排各管道输油量，如何增加最大输油量最大输油量？ 瓶颈瓶颈vsv1v3vtv2v48(8)7(5)9

28、(4)9(9)5(5)6(1)2(0)5(4)10(8)(v1,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9),(vs,1)(- -v2,1)KKW=f *s1+f *s2=8+6=14324324( , )( ,),( ,)( , )5914ttV Vv vv vC V Vcc割集割集容量第第44页页下图中，下图中，A,B,C,D,E,FA,B,C,D,E,F分别表示陆地和岛屿，分别表示陆地和岛屿， 表示桥梁及其表示桥梁及其编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁编号。若河两岸分别为互为敌对的双方部队占领，问至少

29、应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。析。14ABCDEF8911101314127123456最大流问题应用举例最大流问题应用举例在图中任给可在图中任给可行流，用标号行流，用标号法寻找网络最法寻找网络最大流！大流！弧容量：两点间的桥梁数。弧容量：两点间的桥梁数。ABCDFE122211221122ABCDEF8911101314127123456转化为求网络最小割转化为求网络最小割第第46页页 设容量网络设容量网络G G有若干发点，若干个点，有若干发点，若干个点，可以可以添加两个新

30、点添加两个新点vs s，vt t ，用用容量为容量为 的有向边分别连结的有向边分别连结vs s 与发点，收点与与发点，收点与vt t，得到新的网络得到新的网络GG，G G 为只有一个发点，为只有一个发点，一个收点的网络，求解一个收点的网络，求解G G 的最大流问题的最大流问题即可得到即可得到G G的解。的解。多发点多收点网络的最大流问题多发点多收点网络的最大流问题最大流问题应用举例最大流问题应用举例第第47页页 设有设有5位待业者，位待业者，5项工作，他们各自能胜任工作项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽的情况如图所示，要求设计一个就业方案，使尽量多的人能就业量

31、多的人能就业。1x2x3x4x5x1y2y3y4y5y其中其中51,xx 表示工人。表示工人。51,yy 表示工作。表示工作。最大匹配问题最大匹配问题1x2x3x4x5x1y2y3y4y5y图中最大匹配问题，可以转化为最大流问题求解。在图中最大匹配问题，可以转化为最大流问题求解。在图中增加两个新点图中增加两个新点 分别作为发点，收点。并用分别作为发点，收点。并用有向边把它们与原图中顶点相连，令全部边上的容量有向边把它们与原图中顶点相连，令全部边上的容量均为均为1。当网络流达到最大时，如果。当网络流达到最大时，如果 上的流量为上的流量为1，就让就让 作作 工作，此即为最大匹配方案。工作，此即为最

32、大匹配方案。svtv,svtv),(jiyxixjy1x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 (。) 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1