第四节 最大流问题

1第4节网络最大流问题例连接某产品产地vs和销地vt的交通网如下：v1v4115v2vsv3vt325224弧（vi，vj）：从vi到vj的运输线，弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从vs到vt的产品数量最多。2弧旁数字：运输能力。问题：这个运输网络中，从vs到vt的最大输送量是多少？v1v4115v2vsv3vt32522437.4.1最大流的基本概念与定理（1）.网络流网络流对于网络G=（V，A，C），定义在弧集合A上的一个函数f={f(vi,vj)}称为网络流，f(vi,vj)（简称fij）为弧aij∈A上的流。容量：在有向图上，每条弧上给出的最大通过能力（最大可能负载）。cij流量：网络中加在弧上的负载量（实际负载量）。fij4弧旁数字：容量(a)图是一个网络v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁数字：流量5cijfijvivjv2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17,2)(3,2)(5,2)6（2）.可行流可行流满足下述条件的流f称为可行流:1)容量限制条件:对每一弧(vi,vj)∈A0≤fij≤cij2)平衡条件:对中间点vi(i≠s,t),有(,)(,)0ijjiijjivvAvvAff)V(:A),(A),(fffvsjjsvvjsvvsjs)V(:A),(A),(fffvtjjtvvjtvvtjtV(f)称为可行流f的流量,即发点的净输出量。如所有fij=0，零流。可行流总是存在的7（3）.最大流若V（f*）为网络可行流，且满足：V（f*）=Max{V（f）∣f}为网络D中的任意一个可行流，则称f*为网络的最大流。（4）.前向弧与后向弧设μ=（x,…,u，v,…A）是网络G中的一条初等链并且定义链的方向是从x到A。若D中有弧（u，v），与μ方向一致，则称（u，v）为链μ的前向弧，若D中有弧（u，v），与μ方向相反,则称（v,u），为链μ的后向弧。8（5）.增广链对可行流f={fij}：非饱和弧：fijcij饱和弧：fij=cij非零流弧：fij0零流弧：fij=0链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。v2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17,2)(3,2)(5,2)9µ=(v1,v2,v3,v4,v5,v6)µ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}µ-={(v4,v5)}v2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17,2)(3,2)(5,2)10增广链设f是一个可行流,µ是从vs到vt的一条链,若µ满足下列条件,称之为关于可行流f的一条增广链。(vi,vj)∈µ-0fij≤cij后向弧是非零流弧，(vi,vj)∈µ+0≤fijcij前向弧是非饱和弧，v1v2v3v4v5v6(8,4)(6,0)(6,5)(3,3)(5,4)11（6）.截集与截量对于有向网络G=(V,A,C），若S为V的子集，，则称弧集为网络G的一个截集，并将截集中所有弧容量之和称为截容量，即为截集的截容量（简称为截量）。(SS)=a|a=(u,v),uS,vS，aS,SCS,SCa（）（）=（）（7）最小截与最小截量S=V-S(S,S)若是容量网络中所有截集中截量最小的截集，即则称为G上的最小截，为上的最小截量。minCS*S*CSSSSG（,）=（,）|（,）为网络的一个截量S*S*（，）CS*S*（,）S*S*（，）12性质任何一个可行流的流量V(f)都不会超过任一截集的容量。即11()(,)VfCVV可行流f*，截集(V1*，V1*),若V(f*)=C(V1*，V1*），则f*必是最大流，(V1*，V1*)必是D的最小截集。定理若f*是网络G=（V，A，C）上的可行流，则可行流f*为最大的充要条件为μ中不存在关于f*的增广链。最大流最小截量定理。任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。137.4.2寻求最大流的标号法（Ford—Fulkerson）从任一个可行流f出发（若网络中没有给定f，则从零流开始），经过标号过程与调整过程。（一）标号过程未标号点未检查已检查标号点网络中的点14标号：开始，vs标上（0，∞），vs是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi，对一切未标号的点vj。（1）若弧（vi，vj）上，fijcij，则给vj标号(i，l(vj))，l(vj)=min[l(vi),cij-fij],vj成为标号而未检查的点。（2）若弧（vj，vi）上，fji0，则给vj标号(-i，l(vj))，l(vj)=min[l(vi),fji],vj成为标号而未检查的点。fijcijvivj(i,l(vj))l(vj)=min[l(vi),cij-fij],fji0vivj(-i,l(vj))l(vj)=min[l(vi),fji]15重复上述步骤，一旦vt被标号，则得到一条vs到vt的增广链。若所有标号都已检查过，而vt尚未标号，结束，这时可行流，即最大流。（二）调整过程从vt开始，反向追踪，找出增广链µ，并在µ上进行流量调整。（1）找增广链如vt的第一个标号为k（或-k），则弧（vk，vt）∈µ（或弧（vt，vk)∈µ)。检查vk的第一个标号，若为i（或-i），则(vi,vk)∈µ(或(vk,vi)∈µ)。再检查vi的第一个标号,依此下去,直到vs。被找出的弧构成了增广链µ。16（2）流量调整令调整量是l(vt)，构造新的可行流f′，令uvvfuvvfuvvffjiijjiijjiij'ij),(),(),(-去掉所有的标号,对新的可行流f′={fij′},重新进入标号过程。17例用标号法求下图网络的最大流。弧旁的数字是(cij,fij)。解：（一）标号过程。（1）给vs标上（0，∞）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）415minmin111,)fc(),v(l)v(lsss在弧（vs，v2）上，fs2=cs2=3,不满足标号条件。（2）检查vs，在弧（vs，v1）上，fs1=1，cs1=5，fs1cs1,给v1标号(s,l(v1)),其中（vs，4）18（3）检查v1，在弧（v2，v1）上，f210，给v2标号(-1,l(v2)),,,f),v(l)v(l114minmin2112在弧（v1，v3）上，f13=2，c13=2，不满足标号条件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）（vs，4）（-v1，1）（4）检查v2，在弧（v3，v2）上，f32=10，给v3标号(-2,l(v3)),这里,11,1min),(min)(3223fvlvl（-v2，1）19在弧（v2，v4）上，f24=3，c24=4，f24c24,给v4标号(2,l(v4)),其中,,min)fc(),v(l)v(l111min242424（5）检查v3，在弧（v3，vt）上，f3t=1，c3t=2，f3tc3t，给vt标号(3,l(vt)),这里,,min)fc(),v(lmin)v(lttt111333vt得到标号，标号过程结束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,∞）（vs，4）（-v1,1）（-v2,1）(v2，1)(v3，1)20（二）调整过程：从vt开始逆向追踪，找到增广链。µ（vs,v1,v2,v3,vt）=1，在µ上进行流量=1的调整，得可行流f′如右图所示：v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,∞）（vs，4）（-v1,1）（-v2,1）(v2，1)(v3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)21去掉各点标号，从vs开始，重新标号。点v1：标号过程无法进行，所以f′即为最大流。V（f′）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，∞）（vs，3）截集：[V1，V1]=[（vs，v2），（v1，v3）]V（f′）=C[V1，V1]=5V1=(vs,v1)V1=(v2,v3,v4,vt)问题：(v2,v1)是不是截集[V1，V1]中的弧？22例用标号法求下图网络的最大流。弧旁的数字是(cij,fij)。v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)vt23解：第一轮标号过程（1）vs标（0，+∞），vs为已标号未检查点。（2）检查vs，给v2标号（vs，l(v2)），vs成为已标号已检查的点，v2成为已标号未检查的点。（3）检查v2，给v1标号（-v2，l(v1)）。同理给v4标号为（v2，1），v2成为已标号已检查的点，v1，v4成为已标号未检查的点。（4）检查v1，给v3标号为（v1，2），v3成为已标号未检查的点。（5）检查v3，给vt标号为（v3，2）。因为vt已被标号，所以说明找到一条增广链。调整过程按点的第一个标号，以vt点开始，回溯找到一条增广链，如下图红线所示：2)min6-24lv(，1)min42lv(，224vt(0，+∞)（vs，4）（-v2，2）（v2，1）（v1，2）（v3，2）v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)2522'sstvvfvvlv（，）：（，）=2+（）=2+2=4vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)在增广链上进行了流量调整。前向弧后向弧1313'tvvfvvlv（，）：（，）=1+（）=1+2=333'tttvvfvvlv（，）：（，）=3+（）=3+2=51212'tvvfvvlv（，）：（，）=2-（）=2-2=0于是调整后流量如下图所示。(0，+∞)（vs，4）（-v2，2）（v2，1）（v1，2）（v3，2）26v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)vt27第二轮：标号过程（1）vs标（0，+∞），vs为已标号未检查点。（2）检查vs，给v2标号（vs，2），v2成为已标号未检查的点。（3）检查v2，给v4标号（v2，1），v4成为已标号未检查的点。（4）检查v4，给vt标号为（v4，1），vt被标，转入下一阶段。调整过程根据标号过程，以vt点开始，回溯找到一条增广链，如下图红线所示。28vt(0，+∞)v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)（vs，2）（v2，1）（v4，1）29v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)增广链上的三个弧都为前向弧，于是调整如下：于是新调整的流量如下图所示。222242424444'ssst't'ttttvvfvvfvvlvvvfvvfvvlvvvfvvfvvlv（，）：（，）=（，）+（）=4+1=5（，）