问题：

求如图10-36所示的网络的最大流(每弧旁的数字是(c ij ，f ij ))。

---

---

答案：

给中间点标上编号，如图10-37所示。 (1)标号过程。 开始先给v s 标上(0，+∞)，这时，v s 是标号而未检查的点。 第1步：弧(v 1 ，v 4 )，因f s1 =3，c s1 =4，则f s1 ＜c s1 。 则给v 1 标号(v s ，L(v 1 )) L(v 1 )=min{L(v s ),c s1 -f s1 }=min{+∞,4-3)＝1 第2步：检查弧(v 1 ，v 4 )。 f 14 =1，c 14 =1，不满足标号条件，对v 4 不进行标号。 对于弧(v 1 ，v 5 )，f 15 =2，c 15 =3，则f 15 ＜c 15 。 则给v 5 标号(v 1 ，L(v s )) L(v 5 )=min(L(v 1 )，c 15 -f 15 )=min(1，1)=1 第3步：弧(v 5 ，v 4 )，f 54 =3，c 54 =5，则f 54 ＜c 54 。 则给v 4 标号(v 5 ，L(v 4 )) L(v 4 )=min{L(v 5 )，c 54 -f 54 }=min{1，4-3)=1 第4步：对于弧(v 4 ，v t )因f 4t =0，c 4t =7，f 4t ＜c 4t 。 则给v t 标号(v 4 ，L(v t )) L(v t )=min{L(v 4 )，c 4t -f 4t }=min{1，7-6}=1 故 θ＝L(v t )=1 (2)调整过程。 由点的第一个标号找到一条增广链，如图10-38中双箭头线所示。 按θ=1在u上进行调整f： f s1 +1=4，f 15 +1=2+1=3，f 54 +1=4，f 4t +1=7 其余f ij 不变，调整后如图10-39所示。 再对这个可行流进行标号过程，寻找增广链。 (1)标号过程。 开始先给v s 标上(0，+∞)， 第1步：对于(v s ，v 2 )，f s2 =2，c s2 =10，则f s2 ＜c s2 。 则给v 1 标号(v 2 ，L(v 2 )) L(v 2 )=min{L(v 2 ),C s2 -f s2 }=min{+∞，10-4)=6 第2步：对于弧(v 2 ，v 3 )，f 23 =4，c 23 =4，则f 23 ＜c 23 。 则给v 2 标号(v s ，L(v 3 )) L(v3 3 )min{L(v 2 )，c 23 -f 23 )=min{6，4，-2}=2 第3步：对于弧(v 3 ，v t )，f 3t =3，c 3t =8，则f 3t ＜c 3t 。 则给v t 标号(v 3 ，L(v t )) L(v t )=min{L(v 3 ),c 3t -f 3t )=min{2,8-3)=2 故v t 有了标点，转入调整过程。 (2)调整过程。 由点的第一个标号找到一条增广链，双箭头线表示。 根据θ=2，在u上调整f： f s2 +2＝8,f 23 +2＝4,f 3t +2=5 其他f ij 不变，调整后得到如图10-41所示的可行流。对这个可行流进入标号过程，寻找增广链。 首先给v s 标号(0，+∞)。 第1步：对于弧(v s ，v 5 )，f s5 =2，c s5 =3，则f s5 ＜c s3 ，故给v 5 标号(v s ，L(v 5 )。 这里 L(v 5 )=min{L(v s )，L s5 -f s5 }=min{+∞,3-2)=1 第2步：对于弧(v 5 ，v 4 )，f 54 =4，c 54 =4．则v 4 不能标号。 第3步：对于弧(v s ，v 2 )，f s2 =8，c s2 =10，则f s2 ＜c s2 ，给v 2 标号(v s ，L(v 2 ))，这里 L(v 2 )=min{L(v 5 )，c s2 -f s2 }=min{+∞,10-8}=2 第4步：对于弧(v 2 ，v 3 )，f 23 =4，c 23 =4，则f 23 =c 23 ，故v 3 不能标号。 此时，标号无法继续下去，算法结束。此时的可行流即为网络最大流，其最大流为 v(f * )=f s1 +f 54 +f 23 =4+4+4=12。