例题最大流的标号法
例2用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（q,f j）。

.
解：
⑴首先，给V s标上（0,）
⑵检查v s,给v s为起点的未饱和弧的未标号的终点V2标号（V s,l（V2））,其中其它点不符合标号条件。

（3）检查V2，给V2为终点的非零流弧的未标号的起点V3标号（V2,l（V3））,其中其它点不符合标号条件。

⑷检查V3，给V3为起点的未饱和弧的未标号的终点V4、V标号（V4,l（V4））、
（V6,l（V6））其中，1他）min[©3）234 彳34】min[ 4,5 4] 1
其它点不符合标号条件。

⑸检查V6，给V6为起点的未饱和弧的未标号的终点V t标号（V t,l（V t））其中，
其它点不符合标号条件。

由于V t已标号，反向搜索可得增广链｛（V s,V2）,（V3,V2）,（V3,V6）,
（V6,V t）｝，在该增
广链的前相弧（V s,V2）,（V3, V6）,（V6, V t）上增加l（V t） 4，在后向弧（V3,V2）上减去l（V t）4，其它弧上的流量不变，则可得一流量v（f） 20的新的可行流如下图。

V3 (5,5) V6
重新开始标号：
⑹首先，给V s标上（0,）
⑺检查V s,给V s为起点的未饱和弧的未标号的终点V2标号（V s,l（V2））,其中其它点不符合标号条件。

(8)检查V2，没有以V2为起点的未饱和弧的未标号终点和以V2为终点的非零流弧的未标号起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流，最大流的流量为v(f)=20。

事实上，可令V {V s，V2},V i {V3，V4,V5，V6，V t}，则最小截集(V i,V i)的截量
C(V i,V i) C s3 C25 C24 9 5 6 20 V( f)。