例 0(5) 增流 O(8 0(2) +,7) +5 0(10) 2(x,+7)09)v4(2+,7 2n+,5)7(9)n4 (x,+,1) 增流 增流 7(10) 9(10) v2(n+,3)7(9)v4(2+,2) v2,+,1)9(9)v4 定理9.2.2标号算法结束时所得的流是最大流 证明:算法结束时,L=Φ,所有已标顶点都已查,S是所有已标已查顶点的集合。S≠Φ(因 y∈S)。按照标号规则,对va∈(S,S),f(a)=C(a);对va∈(S,S),f(a)=0,(否则可得到新的 标号顶点,算法不会终止)。从而 val f f(a) f(a) f(a) C(a)=Cap(s,S) 由推论9.1,2,∫是最大流,而(S,S)是最小割。证毕 、 Emends-Karp修改标号法: Ford- Fulkerson标号法的缺陷 (1)当弧容量为无理数时,可以构造出例子说明算法不能在有限步终止 见 C H. Papadimitry等著,《 Combinatorial Optimization- Algorithms& Complexity》s63 或谢政著,《网络算法与复杂性理论》,国防科技大学出版社,2003年。 (2)即使弧容量都是有理数或整数,标号算法也不是一个有效算法。 例 可见,标号算法的计算量并不完全依赖于问题的规模v和E,还依赖于容量函数。它不是多项式时 间算法。例： 定理 9.2.2 标号算法结束时所得的流是最大流。 证明：算法结束时， L = Φ ，所有已标顶点都已查，S 是所有已标已查顶点的集合。 S ≠ Φ (因 y ∈ S )。 按照标号规则，对∀∈ = a SS f a Ca ( , ), ( ) ( ) ；对∀a SS fa ∈ = ( , ), ( ) 0 ，(否则可得到新的 标号顶点，算法不会终止)。从而 (,) (,) (,) (,) () () () () (, ) a SS a SS a SS a SS Val f f a f a f a C a Cap S S ∈∈ ∈ ∈ =−=== ∑∑∑∑ 由推论 9.1.2，f 是最大流，而(, ) S S 是最小割。证毕。 三、Edmends－Karp 修改标号法： Ford－Fulkerson 标号法的缺陷： (1) 当弧容量为无理数时，可以构造出例子说明算法不能在有限步终止。 见 C.H.Papadimitry 等著，《Combinatorial Optimization－Algorithms & Complexity》§6.3， 或谢政著，《网络算法与复杂性理论》，国防科技大学出版社，2003 年。 (2) 即使弧容量都是有理数或整数，标号算法也不是一个有效算法。 例： 可见，标号算法的计算量并不完全依赖于问题的规模ν 和ε ，还依赖于容量函数。它不是多项式时 间算法。 v4 v1 v5 v3 x y v2 v6 m m m m m m m m 1 v4 v1 v3 x y v2 0(7) 0(9) 0(8) 0(5) 0(9) 0(2) 0(6) 0(10) 0(5) (x,+,7) (v2,+,7) (x,+,8) (x,+,∞) (v4,+,7) (v1,+,8) v4 v1 v3 x y v2 7(7) 7(9) 0(8) 0(5) 0(9) 0(2) 0(6) 7(10) 0(5) (v1,+,5) (x,+,8) (x,+,∞) (v3,+,5) (v1,+,8) 增流 v4 v1 v3 x y v2 7(7) 7(9) 5(8) 0(5) 5(9) 0(2) 0(6) 7(10) 5(5) (v1,+,3) (v2,+,2) (x,+,3) (x,+,∞) (v4,+,2) (v1,+,3) v4 v1 v3 x y v2 7(7) 9(9) 7(8) 2(5) 5(9) 0(2) 0(6) 9(10) 5(5) (v1,+,1) (x,+,1) (x,+,∞) (v1,+,1) 增流 增流