例题最大流的标号法

精品文档

例题最大流的标号法

例2用标号法求下图所示的公路交通网络的最大流量 (要求写出标号过程并说明得到的的确是最大流)，其中，弧旁的数字是(c「f Q。.

⑴首先,给V s标上(0, ) s, l(V2)),其中

l(V2)min [l(V s),C s2 f s2】min[ ,15 7] 8 其它点不符合标号条件。

(2)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V

⑶检查V2，给V2为终点的非零流弧的未标号的起点V3标号(V2, |(V3)),其中

l(V3)min[g), f32】min[ 8,4] 4 其它点不符合标号条件。

(4)检查v3，给v3为起点的未饱和弧的未标号的终点v4、v6标号(V4, l (V4)) > ( v6,

l(V6))其中，l(V4)min[?3)234 ￡34] min[4,5 4] 1 l(V6)min [l(V3),C36 f36] min [4,5 1] 4 其它点不符合标号条件。

⑸检查v6，给v6为起点的未饱和弧的未标号的终点v t标号(v t, l (v t))其中，

l(V t) mi n[l(V6), C6t f&] mi n[4,10 5] 4 其它点不符合标号条件。 由于

V t

已标号，反向搜索可得增广链{(V

s,V2),(V3,V2),(V3,V6),(V6,Vj}，在该

增广链的前相弧(v s, v2), (v3, v6), (v6,v t)上增加l (v t) 4，在后向弧(v3, v2)上减去

精品文档

l(V t) 4，其它弧上的流量不变，则可得一流量v(f ) 20的新的可行流如下图

重新开始标号： ⑹首先,给V s标上(0, )

(7)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V s, l(V2)),其中

l(V2) min [l(V s),C s2 f s2】 min[ ,15 11] 4 其它点不符合标号条件。

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

事实上，可令V i {V s, V2}, V i ，则最小截集(ViM)的截量 C(V i,V i) C s3 C25 C24 9 5 6 20 V( f)。 精品文档 欢迎您的下载， 资料仅供参考!

致力为企业和个人提供合同协议，策划案计划书，学习资料等等 打造全网一站式需求