34.设v的标号为(k,)。若k≠-1,在AN(n)中删去v的所有入弧,所得网络仍记为 AN(门),令=k,转31:否则,令f叫1=m,P:=P+1,q=0,转 Stepl step4(增流)从顶点V,出发按第一个标号反向追踪,求出AN()的xy路P,将P上每条弧的容量 C改为C-,删去容量为0的弧,同时把流厂增加为流1。将所得网络记为AN(P),并令 q=q+1。去掉网络AN()中所有的标号,转Step3。 例 (3)v6 网络N及其中一个流f6。图例:后,(c) 增量网络N(后6) V23(7) ) (1)p (x)3010)↓3 (y) 辅助网络AN(6)及一条xy路P 沿P增流后的网络流f 增量网络N(f) 辅助网络AN(f)及一条xy路P (7) 4(10 沿P增流后的网络流f° 增量网络N(f°) 辅助网络AN(f0)及一条xy路P 沿P增流后的网络流f 助网络AN(f) AN(f)无x-y路3.4. 设 i v 的标号为(, )i k δ 。若k ≠ −1，在 q p AN f ( ) 中删去 i v 的所有入弧，所得网络仍记为 q p AN f ( ) ，令 i = k，转 3.1；否则，令 : 0 1 q p p f f + = ，p: = p +1， q : , = 0 转 Step1。 Step4. (增流) 从顶点 y v 出发按第一个标号反向追踪，求出 q p AN f ( ) 的 x-y 路 P，将 P 上每条弧的容量 ij c 改为 ij y c −δ ，删去容量为 0 的弧，同时把流 q p f 增加为流 q 1 p f + 。将所得网络记为 q+1 p AN f ( ) ，并令 q: = q +1。去掉网络 q p AN f ( ) 中所有的标号，转 Step3。 例： 网络 N 及其中一个流 f0。图例: f0 ,(c) 增量网络 N ( f0 ) v6 v2 v5 (x) (y) v3 3(10) 3(3) 3(4) 1(1) 2(7) 1(1) 0(5) 4(6) 2(9) 1(5) 0(2) 0(6) v1 v4 v7 v6 v2 v5 (x) (y) v3 7 3 1 1 5 4 2 2 6 v1 v4 v7 3 1 3 1 4 2 5 2 7 v6 v2 v5 (x) (y) v3 3(10) 3(3) 4(4) 1(1) 3(7) 1(1) 0(5) 4(6) 3(9) 1(5) 0(2) 0(6) v1 v4 v7 v2 v5 (x) (y) v3 7 2 v1 v4 v7 1 4 5 7 辅助网络 AN ( f0 )及一条 x-y 路 P 沿 P 增流后的网络流 f1 v6 v2 v5 (x) (y) v3 7 3 1 1 5 4 3 2 6 v1 v4 v7 3 4 1 4 3 4 2 6 v2 v5 (x) (y) v3 1 4 6 6 v1 v4 v7 7 4 增量网络 N ( f1 ) 辅助网络 AN ( f1 )及一条 x-y 路 P v6 v2 v5 (x) (y) v3 4(10) 3(3) 4(4) 0(1) 4(7) 1(1) 0(5) 4(6) 4(9) 1(5) 0(2) 0(6) v1 v4 v7 v6 v2 v5 (x) (y) v3 6 3 1 1 5 4 4 2 6 v1 v4 v7 4 4 1 4 4 3 2 5 增量网络 N ( f1 0 沿 P 增流后的网络流 f ) 1 0 v6 v2 v5 (x) (y) v3 8(10) 3(3) 4(4) 0(1) 4(7) 1(1) 0(5) 4(6) 8(9) 5(5) 0(2) 4(6) v1 v4 v7 v2 v5 (x) (y) v3 3 5 6 v1 v4 v7 6 4 辅助网络 AN ( f1 0 )及一条 x-y 路 P 沿 P 增流后的网络流 f1 1 =f2 v6 v2 v5 (x) (y) v3 2 3 1 1 5 4 8 2 2 v1 v4 v7 8 4 4 5 4 3 2 1 (x) v3 v1 2 辅助网络 AN ( f2) AN ( f2)无 x-y 路