例题 最大流的标 法.docx

例题 最大流的标号法
例 2 用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明
得到的的确是最大流），其中，弧旁的数字是（cij,fij）。 .
v2 （5,5） v5
（6,6） (2,2) （12,7）
（1
例题 最大流的标号法
例 2 用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明
得到的的确是最大流），其中，弧旁的数字是（cij,fij）。 .
v2 （5,5） v5
（6,6） (2,2) （12,7）
（15,7）
vs （4,4） (4,4) vt
(5,4) v4 (4,4)
（9,9) (10,5)
解：
v3           (5,1)           v6
(1) 首先,给 vs 标上(0, + ¥ )
(2) 检查 vs，给 vs 为起点的未饱和弧的未标号的终点 v2 标号(vs, l (v2 ) ),其中
其它点不符合标号条件。
(3) 检查 v ，给 v 为终点的非零流弧的未标号的起点 v 标号( - v , l (v ) ),其中
2 2 3 2 3
其它点不符合标号条件。
(4) 检查 v ，给 v 为起点的未饱和弧的未标号的终点 v 、v 标号( v , l (v ) )、
3 3 4 6 4 4
( v , l (v ) )其中， l (v ) = min[ l (v ), c - f ] = min[ 4,5 - 4] = 1
6 6 4 3 34 34
其它点不符合标号条件。
(5) 检查 v ，给 v 为起点的未饱和弧的未标号的终点 v 标号( v , l (v ) )其中，
6 6 t t t
其它点不符合标号条件。
由于 v 已标号，反向搜索可得增广链 m = {(v , v ), (v , v ), (v , v ), (v , v )} ，在该增
t s 2 3 2 3 6 6 t
广链的前相弧 (v , v ), (v , v ), (v , v ) 上增加 l (v ) = 4 ，在后向弧 (v , v ) 上减去
s 2 3 6 6 t t 3 2
l (v ) = 4 ，其它弧上的流量不变，则可得一流量 v( f ) = 20 的新的可行流如下图。
t
v2 （5,5） v5
（6,6） (2,2) （12,7）
（15,11）
vs （4,0）