第四节 最大流问题

1、1 第第4节节 网络最大流问题网络最大流问题例例 连接某产品产地连接某产品产地vs和销地和销地vt的交通网如下：的交通网如下：v1v4115v2vsv3vt325224弧（弧（vi，vj）：从）：从vi到到vj的运输线，的运输线，弧旁数字：这条运输线的最大通过能力弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从制定一个运输方案，使从vs到到vt的产品数量最多。的产品数量最多。2弧旁数字：弧旁数字：运输能力。运输能力。问题：这个运输网络中，从问题：这个运输网络中，从vs到到vt的最大输送量是多少？的最大输送量是多少？v1v4115v2vsv3vt32522437.4.1最大流的基本概念

2、与定理最大流的基本概念与定理（1）. 网络流网络流网络流网络流 对于网络G=（V，A，C） ，定义在弧集合A上的 一个函数f = f(vi ,vj) 称为网络流， f(vi , vj) （简称fij）为弧aij A上的流。 容量容量：在有向图上，每条弧上给出的最大通过能力（最大可能负载）。cij流量流量：网络中加在弧上的负载量（实际负载量）。 fij4弧旁数字：弧旁数字： 容量容量(a)图是一个网络图是一个网络v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁数字：弧旁数字： 流量流量5 cij fijvivjv2v5(3,3)(4,1)(8,3

3、)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17 ,2)(3,2)(5 ,2)6（2）. 可行流可行流可行流可行流 满足下述条件的流 f 称为可行流:1)容量限制条件: 对每一弧(vi , vj )A 0fij cij2)平衡条件: 对中间点vi (is,t ),有 (,)(,) 0ijjiijjiv vAvvAff)V( : A),(A),(fffvsjjsvvjsvvsjs )V( : A),(A),(fffvtjjtvvjtvvtjt V( f ) 称为可行流 f 的流量,即发点的净输出量。如所有如所有fij=0， 零流。零流。可行流总是可行流总是存在的存在的7（3）

4、. 最大流最大流 若若 V（f *） 为网络可行流，且满足：为网络可行流，且满足： V（f *）=MaxV（f ） f 为网络为网络D中的任意中的任意 一个可行流，则称一个可行流，则称f *为网络的为网络的最大流最大流。（4）.前向弧与后向弧前向弧与后向弧 设设=（x,u，v,A）是网络）是网络G中的一条初等链并且中的一条初等链并且定义链的方向是从定义链的方向是从x到到A。若。若D中有弧（中有弧（u，v），与），与方向方向一致，则称（一致，则称（u，v）为链）为链的的前向弧前向弧，若，若D中有弧（中有弧（u，v），与），与方向相反方向相反,则称（则称（v, u），为链），为链的的后向弧后向弧。

5、8（5）. 增广链增广链对可行流 f = fij ：非饱和弧：fij 0零流弧：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

6、是一个可行流, 是从vs 到vt 的一条链,若满 足下列条件,称之为关于可行流 f 的一条增广 链。(vi , vj ) - 0 fij cij 后向弧 是非零流弧，(vi , vj ) + 0 fij cij 前向弧是 非饱和弧，v1v2v3v4v5v6(8,4)(6,0)(6,5)(3,3)(5,4)11（6）. 截集与截量截集与截量 对于有向网络对于有向网络G=(V,A,C） ，若，若S为为V的子集，的子集， ，则称弧集则称弧集 为网络为网络G的一个截集，并将截集中所有弧容量之和称为截容量，的一个截集，并将截集中所有弧容量之和称为截容量，即即 为截集为截集 的的截容量截容量（简称为截量）

7、。（简称为截量）。(SS)= a|a=(u,v),uS,vS，aS, SC S, SC a（）（）=（ ）（7）最小截与最小截量）最小截与最小截量 S=V - S(S,S ) 若若 是容量网络中所有截集中截量最小的截集，即是容量网络中所有截集中截量最小的截集，即 则称则称 为为G上的上的最小截最小截， 为上的为上的最小截量最小截量。minC S* S*C S SS SG（,）=（ , ）|（ , ）为网络 的一个截量S*S*（，）C S* S*（,）S*S*（，）12 性质性质 任何一个可行流的流量任何一个可行流的流量V(f)都不会超过任一截集的容都不会超过任一截集的容量。即量。即11 ( )

8、( ,)V fC V V可行流可行流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寻求最大流的标号

9、法（寻求最大流的标号法（FordFulkerson） 从任一个可行流从任一个可行流 f 出发（若网络中没有给定出发（若网络中没有给定 f ，则从零流开始），经过标号过程与调整过程。则从零流开始），经过标号过程与调整过程。（一）标号过程（一）标号过程 未未标标号号点点未未检检查查已已检检查查标标号号点点网网络络中中的的点点14标号：标号： 开始，开始，vs 标上（标上（0，），），vs 是标号未检查的点，是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查其余点都是未标号点，一般地，取一个标号未检查的点的点vi ，对一切未标号的点，对一切未标号的点vj 。（1）若弧（）若弧（vi，vj

10、）上，）上，fij0，则给，则给vj 标号标号(-i， l (vj)，l (vj)=minl (vi), fji, vj 成为标号而未检查的点。成为标号而未检查的点。fij0vivj(-i , l(vj)l(vj)=minl(vi),fji15 重复上述步骤，一旦重复上述步骤，一旦vt被标号，则得到一条被标号，则得到一条vs到到vt的的增广链。若所有标号都已检查过，而增广链。若所有标号都已检查过，而vt尚未标号，结束，尚未标号，结束，这时可行流，即最大流。这时可行流，即最大流。（二）调整过程（二）调整过程 从从vt 开始，反向追踪，找出增广链开始，反向追踪，找出增广链 ，并在，并在上进上进行流

11、量调整。行流量调整。（1）找增广链）找增广链 如如vt 的第一个标号为的第一个标号为k（或或-k），），则弧（则弧（vk，vt）（或弧（或弧（vt，vk) )。检查。检查vk 的第一个标号，若为的第一个标号，若为i（或（或-i），则），则(vi,vk) (或或(vk,vi) )。再检查。再检查vi 的第一的第一个标号个标号,依此下去依此下去,直到直到vs 。被找出的弧构成了增广链。被找出的弧构成了增广链 。16（2）流量调整）流量调整令调整量令调整量 是是 l(vt)，构造新的可行流，构造新的可行流 f ，令令 uvv fuvvfuvvffjiijjiijjiijij ),( ),( ),(

12、- 去掉所有的标号去掉所有的标号,对新的可行流对新的可行流 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）检查）检查

13、vs，在弧（，在弧（vs，v1）上，）上，fs1=1，cs1=5， fs10， 给给v2标号标号 (-1, l 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)(3223fvl

14、vl（-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,）（

15、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去

16、掉各点标号，从去掉各点标号，从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 ）=CV1，V1=5V1=(vs,v1) V1=(v2,v3,v4, vt)问题：问题：(v2,v1)是不是截集是不是截集V1，V1中的弧？中的弧？22例例 用标号法求下图网络的最大流。弧旁的数字是用标号法求下图网络的最大流

17、。弧旁的数字是( 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成为已标号已检查的成为已标号已检查的 点，点，

18、v1，v4成为已标号未检查的点。成为已标号未检查的点。（4）检查）检查v1，给，给v3标号为（标号为（v1，2），），v3成为已标号未检成为已标号未检 查的点。查的点。（5）检查）检查v3，给，给vt标号为（标号为（ v3 ，2）。）。 因为因为vt已被标号，所以说明找到一条增广链。已被标号，所以说明找到一条增广链。 调整过程调整过程 按点的第一个标号，以按点的第一个标号，以vt点开始，回溯找到一条增广点开始，回溯找到一条增广 链，链， 如下图红线所示：如下图红线所示：2)min6-24l v (，1)min 42l v(，224vt(0， +)（vs，4）（-v2，2）（v2，1）（v1，2

19、）（v3，2）v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)2522sstvv fvvl v（ ， ） ： （ ， ）=2+（ ）=2+2=4vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)在增广链上进行了流量调整。在增广链上进行了流量调整。前向弧前向弧 后向弧后向弧 1313tvv fvvl v（ ， ） ： （ ， ）=1+（ ）=1+2=333tttvv fvvl v（ ， ） ： （ ， ）=3+（ ）=3+2=51212tvv fvvl v（ ， ） ：

20、（ ， ）=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点开始，回溯找到一条增广链，如点开始，回溯找到一条增广链，如 下图红线所示。下图红线所示。2