(8.4.2)--08_4_2最大流问题的标号法.pdf

《(8.4.2)--08_4_2最大流问题的标号法.pdf》由会员分享，可在线阅读，更多相关《(8.4.2)--08_4_2最大流问题的标号法.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、求最大流的标号法 从网络中的一个可行流f 出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f 的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的。以便找出增广链。第二个标号是为了用来确

2、定增广链上的调整量。标号过程开始，先给vs标号（0，+）。这时，vs是标号未检查的点，其他都是未标号点。1 给发点vs标号（0，+）。2 取一个已标号的点vi，对于vi一切未标号的邻接点vj按下列规则处理：（1）如果边，且那么给vj标号，其中：（2）如果边，且，那么给vj标号，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。标号过程:Avvij),(0i jf),(jilv),min(ii jjlfl Avvji),(ijijcf),(jilv),min(ij ij

3、 ijlfcl调整过程设1令2去掉所有标号，回到第一步，对可行流重新标号。(Cij,fij)v4v1v2v 3vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）v t例:求图中网络最大流，弧旁的权数表示（cij,fij）。解.用标号法。1.标号过程。（1）首先给vs标号（0，+）（2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故给v2标号（-v1,l(v2),其中l(v2)=minl(v1),f21=min4,1=1.(Cij,fij)v4v1v2v 3vs（2,1）（3,0）（4,3）（3

4、,3）（5,1）（2,2）（5,3）（1,1）（1,1）v t（4）看v2:在弧（v2,v4）上，f24=30,故给v3标号（-v2，l(v3),其中l(l(v3)=minl(v2),f32=min1,1=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1c3t=2,故给vt标号(v3,l(vt),其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt被标上号，根据标号法，转入调整过程。(Cij,fij)(v3,1)V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）Vt(0，+)(

5、-v1,1)(vs,4)(-v2,1)(v2,1)2.调整过程从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图中箭线所示。不难看出:+=(vs,v1),(v3,vt),-=(v2,v1),(v3,v2),取=1，在上调整f，得到fs1+=1+1=2在+上f3t+=1+1=2在+上f*=f21-=1-1=0在-上f32-=1-1=0在-上其他的不变(Cij,fij)(v3,1)V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）Vt(0，+)(-v1,1)(vs,4)(-v2,1)(v2,1)调整后

6、的可行流f*，如图所示，再对这个可行流从新进行标号过程，寻找增广链。首先给vs标号（0，+），看vs,给v1标号（vs,3）。看v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合条件。因此标号过程无法进行下去，不存在从VS到Vt的增广链，算法结束。这时，网络中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同时，也找出D的最小截集（V1，V1），其中V1是标号的集合，V1是未标号的集合。V4V1V2V3Vs（2,2）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+)(vs,3)(Cij,fij)（1,0）最小截集最大流f*=5