数学建模_网络最大流问题

1、基本概念与基本定理寻求最大流的标号法在许多实际的网络系统中都存在着在许多实际的网络系统中都存在着流量和最大流问题流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题例如铁路运输系统中的车辆流，城市给排水系统的水流问题, ,控制系统中的信息流问题，常见的人流，物流，水流，气流，控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。电流，现金流等。在一定条件下在一定条件下, ,求解给定系统的最大流量求解给定系统的最大流量, ,就是网络最大流问题就是网络最大流问题. .网络系统最大流问题是图与网络理论中十分重要的最优化问网络系统最大流问题是图与网络理论中十分重要的最

2、优化问题，它对于解决生产实际问题起着十分重要的作用。题，它对于解决生产实际问题起着十分重要的作用。一一 引言引言连通网络连通网络 G G( (V, AV, A) ) 中有中有 m m 个节点个节点, , n n条弧条弧, , 弧弧 e eij ij 上的流量上界为上的流量上界为 c cij ij , , 求从起始节点求从起始节点 v vs s 到终点到终点 v vt t 的最大流量的问题就是的最大流量的问题就是 最大流问题最大流问题。 连接某产品产地连接某产品产地v v1 1和销地和销地v v6 6的交通网如下：的交通网如下：v2v5348v3v1v4v65106111735（a）弧（弧（v

3、vi i，v vj j）：从）：从v vi i到到v vj j的运输线，的运输线，弧旁数字：这条运输线的弧旁数字：这条运输线的最大最大通过能力通过能力容量容量。v2v5313v3v1v4v61563222（b）制定一个运输方案，使从制定一个运输方案，使从v v1 1运到运到v v6 6的产品数量的产品数量最多。最多。弧旁数字：运输数量弧旁数字：运输数量流量流量。问题：这个运输网络中，从问题：这个运输网络中，从v v1 1到到v v6 6的最大输送量是多少？的最大输送量是多少？设一个赋权有向图设一个赋权有向图D=D=（V, AV, A）, ,在在V V中指定一个中指定一个发点发点v vs s和一

4、个和一个收点收点v vt t , ,其它的点叫做其它的点叫做中间点中间点。对于对于D D中的每一个弧（中的每一个弧（v vi i , , v vj j）A A , ,都有一个非负数都有一个非负数c cij ij , ,叫做叫做弧的容量弧的容量。我们把这样的图我们把这样的图D D叫做一个叫做一个容量网络容量网络，简称简称网络网络，记做，记做D D=（V V，A A，C C）。）。弧的容量弧的容量：是对网络上的每条弧是对网络上的每条弧(v(vi i,v,vj j) )都给出一个最大的通过能力，都给出一个最大的通过能力，记为记为c (vc (vi i,v,vj j) )或简写为或简写为c cij i

5、j 。二、二、 基本概念基本概念stst对有对有多个发点和多个收点多个发点和多个收点的网络的网络, ,可以另外可以另外虚设一个总发点和一个总收点虚设一个总发点和一个总收点, ,并将其分别与各发点、收点连起来（见图），并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络所以一般只研究具有一个发点和一个收点的网络流流：加在网络各条弧上的一组负载量：加在网络各条弧上的一组负载量f f(v(vi i,v,vj j) )：加在弧：加在弧(v(vi i,v,vj j) )上的负载量上的负载量简

6、记为简记为f fij ij，为非负数，为非负数网络上的流网络上的流：是指定义在弧集合上的一个函数是指定义在弧集合上的一个函数f=f(vf=f(vi i,v,vj j),),其中其中f(vf(vi i,v,vj j) )称为称为弧（弧（v vi i,v,vj j) )上的流量上的流量，流也可看作一个双下标变量流也可看作一个双下标变量v弧的弧的流量流量f f(v(vi i,v,vj j) )：表示弧：表示弧(v(vi i,v,vj j) )上每单位时间内的上每单位时间内的 实际通过能力实际通过能力v弧的弧的容量容量c(vc(vi i,v,vj j) )：表示弧（：表示弧（v vi i,v,vj j

7、) )上每单位时间内的上每单位时间内的 最大通过能力最大通过能力v零流：网络上零流：网络上所有的所有的f fij ij = 0= 0图图10-2410-24表示的就是这个网络上的一个流（运输方案），表示的就是这个网络上的一个流（运输方案），每一个弧上的流量每一个弧上的流量f fij ij就是运输量。就是运输量。例如：例如：f f1212=1 , f=1 , f1313=2 , f=2 , f2424=3 =3 等等。等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt图图10-2410-24v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6

8、）（1）（1）（2）fijvt对于实际的网络系统上的流，有几个显著的特点：对于实际的网络系统上的流，有几个显著的特点：(1)(1)发点的净流出量和收点的净流入量必相等。发点的净流出量和收点的净流入量必相等。(2)(2)每一个中间点的流入量与流出量的代数和等于零。每一个中间点的流入量与流出量的代数和等于零。(3)(3)每一个弧上的流量不能超过它的最大通过能力每一个弧上的流量不能超过它的最大通过能力 （即容量）（即容量）称满足下列条件的流为称满足下列条件的流为可行流可行流：（1 1）容量限制条件）容量限制条件：对于每一个弧（：对于每一个弧（v vi i ,v ,vj j）A A有有 0 0 f f

9、(v(vi i,v,vj j) ) c c(v(vi i,v,vj j) ) （简记为（简记为0 0 f fij ij c cij ij） A)v,v(A)v,v(sjjsjssj)f (vff A)v,v(A)v,v(t jjtjttj)f (vff（2 2）平衡条件）平衡条件：对于对于发点发点v vs s，有，有 对于对于收点收点v vt t ，有，有式子中式子中V(f)V(f)称为可行流称为可行流f f的流量的流量, ,即发点的净输出量即发点的净输出量（或收点的净输入量）。（或收点的净输入量）。对于对于中间点中间点: : 流入量流入量=流出量。流出量。即对每个即对每个i(is,t)i(i

10、s,t)有有 f f(v(vi i,v,vj j) - ) - f f(v(vj j,v,vi i)=0(i)=0(i s s，t t) ) ( (简记为简记为 f fij ij- - f fji ji= 0(i= 0(i s s，t t) ) ) 即总流量即总流量=发点的净输出量发点的净输出量=收点的净输入量收点的净输入量v容量网络的可行流总是存在的，容量网络的可行流总是存在的，v如当所有弧的流均取零，即对所有的如当所有弧的流均取零，即对所有的i,j,i,j,有有f(vf(vi i,v,vj j)=0)=0就是一个可行流就是一个可行流可行流中可行流中 f f ij ijc c ij ij 的

11、弧叫做的弧叫做饱和弧饱和弧，f f ij ijc c ij ij的弧叫做的弧叫做非饱和非饱和弧。弧。f f ij ij0 0 的弧为的弧为非零流弧非零流弧，f f ij ij0 0 的弧叫做的弧叫做零流弧。零流弧。2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) 图中图中 为零流弧，都是非饱和弧。为零流弧，都是非饱和弧。) , (63vv就是要求一个流就是要求一个流f fij ij , ,使其流量使其流量v(f)v(f)达到最大达到最大, ,并并且满足且满足 0 0 f fij ij c cij ij ti)f (

12、vt , si0si)f (vffjiij网络的最大流网络的最大流: :求网络的最大流，即是指满足容量限制条件和平求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使衡条件的条件下，使v(f)v(f)值达到最大值达到最大. .容量网络容量网络D D，若，若为网络中从为网络中从v vs s到到v vt t的一条链，的一条链， 给给定向为从定向为从v vs s到到v vt t，上的弧分为两类：上的弧分为两类：凡与凡与方向方向相同相同的称为的称为前向弧前向弧，凡与凡与方向方向相反相反的称为的称为后向弧后向弧，其集合分别用其集合分别用+ +和和- -表示。表示。 链的方向链的方向：若：若是联结

13、是联结v vs s和和v vt t的一条链，的一条链， 定义链的方向是从定义链的方向是从v vs s到到v vt t。 s st tf f1 1cc1 1f f4 4cc4 4f f5 5c00f f3 300增广链增广链：f f 是一个可行流，如果满足：是一个可行流，如果满足： )v,v(cf0)v,v(cf0jij ij ijij ij i即即 中的每一条弧都是非饱和弧中的每一条弧都是非饱和弧 即即 中的每一条弧都是非零流弧中的每一条弧都是非零流弧 则称则称为从为从v vs s到到v vt t 的关于的关于f f 的一条的一条增广链增广链。s st tf f1 1cc1 1f f4 4cc

14、4 4f f5 5c00f f3 300v2v53-34-18-3v3v1v4v65-110-511- 66-317-23-25-2=(v1,v2,v3,v4,v5,v6)+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)-=(v5,v4)后向弧后向弧2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) 7766633232211),( ,),( ,),( ,),( ,vvvvvvvvvvvvv ),(),(),(766321vvvvvv ),(23vv 是一个增广链是一个增广链显然图中增广链不止一条显

15、然图中增广链不止一条 容量网络容量网络D =D =（V V，A A，C C），），v vs s为始点，为始点，v vt t为终点。为终点。 如果把如果把V V分成两个非空集合分成两个非空集合 使使 ，则所有始点属于，则所有始点属于V V1 1，而终点，而终点 属于属于 的弧的集合的弧的集合 称为是分离称为是分离v vs s和和v vt t的的 截集（或割）截集（或割）11V,V1t1sVv,Vv )V,V(111Vv2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(6)6（30)17(2)3（2）5（2）=(v1,v2,v3)V1V1=(v4,v5,v6) =(v1,v2,

16、v3)V1V1=(v4,v5,v6)截集为红色弧集：截集为红色弧集： )v,v( , )v,v( , )v,v( , )v,v()V,V(5343425211 v2vv3v1v4v65.110.511.66.3)V,V(11vsv1v2v4v3vt374556378V1)v,v(V2s1 )v,v,v,v(Vt4311 )v,v( , )v,v( , )v,v()V,V(32421s11 18567www)V,V(C23241s11 )V,V(C11截集截集 中所有弧的容量之和，称为这个中所有弧的容量之和，称为这个截集截集 的容量的容量，记为，记为 )V

17、,V()j,i(ji1111)v,v(c)V,V(c，也称，也称截量截量，则有：，则有：2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1) )v,v(),v,v(),v,v()V,V(75423121 设设 5211,vvvV 则截集为：则截集为： 76432,vvvvV 不不是是该该集集中中的的弧弧和和而而 )v,v( )v,v( 5423截量为截量为24242v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设设， 211,vvV 则截集

18、为则截集为 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 截量为截量为2020s sv v2 2v v4 4v v3 3v v1 1t t7(5)7(5)8(8)8(8)9(4)9(4)5(4)5(4)2(0)2(0)9(9)9(9)6(1)6(1)10(8)10(8)5(5)5(5)截集与可行流无关，而只与网络本身有关截集与可行流无关，而只与网络本身有关最小截最小截量是个定值量是个定值对应的截量也不相同，对应的截量也不相同，其中截量最小的截集称为其中截量最小的截集称为最小截集最小截集。 设设f f 为网络为网络D=D=（V V，A A，C C）的任一可

19、行流，）的任一可行流， 流量为流量为v(f)v(f)，)V,V(C)f (v11 )V,V(11为任一截集，则有为任一截集，则有结论结论1 1：由于由于V V与与V V的分解方法不同，所以截集就不相同的分解方法不同，所以截集就不相同即任何一个可行流的流量都不会超过任一截集的容量即任何一个可行流的流量都不会超过任一截集的容量)V,V(C)f (v*1*1* 满足条件满足条件那么那么f f * * 一定是一定是D D上的最大流，而上的最大流，而如果网络上的一个可行流如果网络上的一个可行流f *,和网络中的一个截集和网络中的一个截集 )V,V(*1*1一定是一定是D D的最小截集的最小截集。 )V,

20、V(*1*1结论结论2 2： 可行流可行流f f 是是D D的最大流的充分必要条件的最大流的充分必要条件 是是不存在不存在从从v vs s到到v vt t 的关于的关于f f 的一条的一条增广链增广链。 在网络中在网络中s st t的最大流量等于它的的最大流量等于它的最小割集最小割集的的容量，即容量，即*)V*,V(c)f (v* 定理定理9 9 最大流最小截量定理：最大流最小截量定理：最小截集的容量最小截集的容量最大流的流量最大流的流量网络中可行流的流量网络中可行流的流量网络网络割所含弧的流量和割所含弧的流量和割所含弧的容量和割所含弧的容量和弧的流量弧的流量f(vf(vii,v,vj j)

21、)弧的容量弧的容量c(vc(vii,v,vj j) )弧弧(v(vi i,v,vj j) )f(V,V)*v (f)=f (V,V)-f (V,V)*c (V,V)v(f )c (V,V)(V,V)割割 定理定理8 8为我们提供了一个寻求网络系统最大流为我们提供了一个寻求网络系统最大流 的方法。的方法。亦即，如果网络亦即，如果网络D D中有一个可行流中有一个可行流 f f，只要判断网络是否存在关于可行流只要判断网络是否存在关于可行流 f f 的增广链的增广链 。如果没有增广链，那么如果没有增广链，那么f f一定是最大流。一定是最大流。如有增广链，那么可以按照定理如有增广链，那么可以按照定理 8

22、 8中必要性，中必要性，不断改进和增大可行流不断改进和增大可行流f f 的流量，的流量，最终可以得到网络中的一个最大流。最终可以得到网络中的一个最大流。这种算法由这种算法由Ford Ford 和和 FulkersonFulkerson于于19561956年提出年提出, , 故又称故又称Ford Ford Fulkerson Fulkerson标号法；标号法；实质实质：判断是否存在增广链判断是否存在增广链, ,并设法把增广链找出来并设法把增广链找出来, ,并予以调整并予以调整, ,最终使图中无增广链最终使图中无增广链. .二寻求最大流的标号法二寻求最大流的标号法此算法从网络中的一个此算法从网络中

23、的一个可行流可行流f f 出发（如果出发（如果D D中中 没有没有 f f，可以令，可以令f f 是零流），运用标号法，是零流），运用标号法，经过经过标号过程和调整过程标号过程和调整过程，最终可以得到网络中的一个最大流。最终可以得到网络中的一个最大流。 下面用给顶点标号的方法来定义下面用给顶点标号的方法来定义 定理定理8 8中的中的V V1 1* *. .在标号过程中，在标号过程中，有标号有标号的顶点的顶点是是V V1 1* *中的中的点点，没有标号没有标号的点的点不是不是V V1 1* *中的点。中的点。如果如果v vt t有了标号有了标号，表示，表示存在存在一条关于一条关于f f 的的增广

24、链增广链。如果标号过程无法进行下去，并且如果标号过程无法进行下去，并且v vt t未被标号未被标号，则表示则表示不存在不存在关于关于f f 的的增广链增广链。此时，就得到了网络中的一个最大流和最小截集。此时，就得到了网络中的一个最大流和最小截集。在标号过程中，网络中的点分为两种：在标号过程中，网络中的点分为两种：已已标号的点（分为已检查和未检查）和标号的点（分为已检查和未检查）和未未标号的点。标号的点。每个标号点的标号包含两部分：每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，第一个标号表示这个标号是从那一点得到的，以便找出增广链。以便找出增广链。第二个标号是从上一个标号点

25、到这个标号点的流量的第二个标号是从上一个标号点到这个标号点的流量的最大允许调整值最大允许调整值，是为了用来确定增广链上的调整量是为了用来确定增广链上的调整量。 标号过程开始，先给标号过程开始，先给v vs s 标号（标号（0 0，+）。）。这时，这时，v vs s 是标号未检查的点，其它都是未标号点。是标号未检查的点，其它都是未标号点。一般地，取一个标号未检查点一般地，取一个标号未检查点v vi i，对一切未标号点，对一切未标号点v vj j1 1 标号过程标号过程vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1) 求图求图10-

26、2510-25的网络最大流，弧旁的权数的网络最大流，弧旁的权数 表示（表示（c cij ij , f, fij ij）。）。 1. 1. 标号过程。标号过程。1 1）首先给首先给v vs s标号（标号（0 0，+） 2 2）看看v vs s : : 在弧在弧( (v vs s ,v,v2 2) )上上, ,f fs2s2=c cs3s3=3 , =3 , 不具备标号条件。不具备标号条件。 在弧在弧( (v vs s ,v,v1 1) )上上 , , f fs1 s1=1 =1 0 ,=1 0 , 故给故给v v2 2标号（标号（- -v v1 1 , , l l( (v v2 2) )）, ,

27、 其中其中l l ( (v v2 2 )=min)=minl l( (v v1 1) , ) , f f21 21 = min 4 , 1 = 1 = min 4 , 1 = 1. v v2 2标号（标号（-v-v1 1 , 1 , 1），），此时此时v v1 1为已检查的标号点为已检查的标号点vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+ )(v1,1)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+ )(vs,4)(v1,1)(v

28、2,1)(-v2,1)(v3,1)（4 4）看看v v2 2: :在弧（在弧（v v2 2 ,v,v4 4）上，）上，f f2424 =3 =3 0 ,=1 0 , 故给故给v v3 3标号（标号（- -v v2 2，l l( (v v3 3) , ) , 其中其中 l l ( (l l( (v v3 3 )= min)= minl l( (v v2 2) , ) , f f3232 = min1 , 1 =1 = min1 , 1 =1。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+ )(vs,4)(v1,1)(v2

29、,1)(-v2,1)(v3,1)（5 5）在在v v3 3 ,v,v4 4中任意选一个，中任意选一个， 比如比如v v3 3 , ,在弧（在弧（v v3 3 , v, vt t）上，）上，f f3t3t =1 =1 c c3t 3t =2,=2, 故给故给v vt t标号标号( (v v3 3 , ,l l( (v vt t),), 其中其中l l( (v vt t)=min)=minl l( (v v3 3),(),(c c3t3t- -f f3t3t)=min1,1=1.)=min1,1=1. 因为因为v vt t被标上号，根据标号法，被标上号，根据标号法，转入调整过程转入调整过程。 （1

30、 1）如果在如果在前向弧（前向弧（v vi i ,v,vj j）上，有上，有f fij ij 0, 0,那么给那么给v vj j标号（标号（- -v vi i , , l l( (v vj j) )）. .其中其中l l (v(vj j)=min )=min l l( (v vi i), ), f fji ji . .这时，这时，v vj j 成为成为标号未标号未检查检查点。点。 于是于是v vi i 成为成为标号已标号已检查的点。检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。无法进行下去，则标号法

31、结束。这时的可行流就是最大流。这时的可行流就是最大流。但是，如果但是，如果v vt t 被标上号，表示得到一条增广链被标上号，表示得到一条增广链，转入下，转入下一步一步调整过程调整过程。利用反向追踪找增广链，调整增广链的流量，利用反向追踪找增广链，调整增广链的流量， 去掉旧的标号，对新的可行流重新进行标号。去掉旧的标号，对新的可行流重新进行标号。具体做法如下：具体做法如下：（1 1） 按照按照v vt t 和其它已检查的标号点的第一个标号，和其它已检查的标号点的第一个标号，反向追踪，找出增广链反向追踪，找出增广链 ，确定调整量，确定调整量。（2)2)得新的可行流。得新的可行流。 (3)(3)再

32、去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f f =f f ij ij, ,重新重新进行标号过程，直到找到网络进行标号过程，直到找到网络D D的最大流为止。的最大流为止。iiif,ff,f , 所所有有再再令令所所有有非增广链上的弧非增广链上的弧vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(5,2)(1,0)(1,0)(2,2)(cij,fij)f * * = =f fs1 s1 + + =1+1=2 =1+1=2 在在+ +上上f f3t 3t + + =1+1=2 =1+1=2 在在+ +上上 f f *

33、 *= = f f21 21 =1 =1 1=0 1=0 在在- -上上f f3232 = 1 = 1 1=0 1=0 在在- -上上其它的不变其它的不变 调整后的可行流调整后的可行流f f * *如图如图, ,再对这个再对这个 可行流从新进行标号过程，寻找增广链。可行流从新进行标号过程，寻找增广链。一直到标号过程无法进行下去，一直到标号过程无法进行下去，不存在从不存在从v vS S到到v vt t的增广链，算法结束。的增广链，算法结束。vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)vsv1v2v3v4vt(

34、3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij,fij)(0,+ )(vs,3)最大流的流量最大流的流量v v( (f f * * )= )= f fs1 s1+ +f fs2s2=5.=5.最小截集最小截集它的容量也为它的容量也为5.5.1V1V得到的截集为得到的截集为最小截集最小截集（V V1 1， ），其中），其中V V1 1是标号的集合，是标号的集合， 是未标号的集合。是未标号的集合。此时，网络中的可行流此时，网络中的可行流f f * * 即是即是最大流最大流，sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)

35、10(8)5(5)(0,(0, ) )(s,(s,2 2) )(-v(-v2 2, ,2 2) )(v(v1 1, ,2 2) )(-v(-v3 3, ,1 1) )(v(v4 4, ,1 1) )918)t(ff011)t(ff514)t(ff314)t(ff615)t(fft4t44343131312122s2s 用标号法求下图中用标号法求下图中stst的最大流量的最大流量, ,并找出该网络并找出该网络的最小割的最小割. .(v(v2 2)=min)=min(s),(c(s),(cs2s2-f -fs2s2)=2)=2(v(v1 1)=min)=min(v(v2 2),f),f1212=

36、min2,4=2= min2,4=2(v(v3 3)=min)=min(v(v1 1), (c), (c1313- -f f1313)=min2,5=2)=min2,5=2(v(v4 4)=min)=min(v(v3 3),f),f4343= min2,1=1= min2,1=1(t)=min(t)=min(v(v4 4), (c), (c4t4t-f -f4t4t)= min1,2=1)= min1,2=1sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)V*(f)=)V,V(c*sv2v4v3v1t7(6)8(8)9(5)5(3)2(0)9(9)

37、6(0)10(9)5(5)(-v(-v2 2, ,1 1) )(0, (0, ) )(v(v1 1, ,1 1) )(s,(s,1 1) )KKst134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(0+, )(s+,6)(2 ,6)(3+,1)(4+,1)(0+, )(s+,5)(2+

38、,2)(5 ,2)(4+,2)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(0+, )(s+,3)(2 ,3)最小截集最小截集 求下图所示网络的最大流求下图所示网络的最大流vsv1vtv5v4v3v24310413354278给定初始可行流为全零流，即给定初始可行流为全零流，

39、即 f f （0 0） = 0= 0给给v vs s 标号（标号（0 0，+），检查），检查 v vs s ： 给给 v v1 1 标号标号( (v vs s ,4) , ,4) , 给给 v v2 2 标号标号( (v vs s , 3) , , 3) , 给给 v v3 3 标号标号( (v vs s , 10) , , 10) , vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(0,+ )(vs,4)(vs,3)(vs,10)检查检查 v v1 1 ：给：给 v v4 4 标号标号(

40、(v v1 1 , 1) , 1) ，检查完毕；，检查完毕；(v1,1)检查检查 v v2 2 ：给：给 v v5 5 标号标号( (v v2 2 , 3) , 3) ，检查完毕；，检查完毕；vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(v2,3)检查检查 v v5 5 ：给：给 v vt t 标号标号( (v v5 5 , 3) , 3) ，检查完毕；，检查完毕；(v5,3)因为终点因为终点 v vt t 已标号，故找出一条从已标号，故找出一条从v vs s到到v vt t的增广链的增广

41、链： v vs s v v2 2 v v5 5 v vt t . . 取取 = 3= 3vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(vs,4)(v1,3)(vs,10)(v1,1)vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）(v2,2)(0,+ )(v5,2)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(vs,2)(v3,3)(vs,10)(v2,3)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(v3,4)(0,+ )(v4,3)vsv1vtv5v4v3v2（4,2）（10,