f∫(x)-f-(x)≥0 f(y)=f+(y)-f(y)≤0 f(u)=f(a)-f(l)=0 的流 定理93.1设∫是网络N中的一个可行流。则 (1)N中∫可增路与N()中的x-y有向路一一对应。 (2)N中∫可增路P的可增流值4(P)等于N()中对应的x-y有向路P上最小的弧容量 证明:显然 定理93.2设∫”是网络N中的最大流,厂是N中的一个可行流,则增量网络N(f)中的最大流的流值为 lalf-alf。 证明:考虑N(∫)中的任一个割(S,S),对V(l,v)∈(S,S),要么c(l,v)=∫(V,l);要么 v)=c(l,v)-f(u,v)【见注(1)】 令:A1={(l,v)∈(S,S)lc(u,v)=f(v,)}, 4=(05100(::)(:: 非零非饱和弧 则A1∩A2=p且A1UA2=A( 零流弧 (n)=∑c(nv)+∑c(n,) N N ∑f(,n)+∑(c(nr)-f(2) ∑c(un)+∑f(v,)-∑f(u,") S, S)+f(S)-f(S)=Cap(S, S)-Valf 当∫给定后 min Cap(S,S)= min Cap(S,S)-alf。由最大流最小割定理,alf”=lal∫”-half 其中广”表示N()中的最大流 二、网络顶点的分层 设网络N=(,x,y,A,C,令:V={∈Vkx到v的最短有向路的长为l}。设x到y的最短有向路 的长为n,则(1)x∈l0,y∈Vn;(2)V1∩V=,(≠)。H中的顶点称为网络N的第层顶点 注:这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路 例 网络N 网络N的分层 V={x},V={v1,v2},F2={v() () () 0 () () () 0 () () () 0 fx f x f x fy f y f y fu f u f u + − + − + − ⎧ = − ≥ ⎪ ⎨ = − ≤ ⎪ = − = ⎩ 的流。 定理 9.3.1 设 f 是网络 N 中的一个可行流。则 (1) N 中 f 可增路与 N ( f )中的 x − y 有向路一一对应。 (2) N 中 f 可增路 P 的可增流值 Δf ( ) P 等于 N ( f )中对应的 x − y 有向路 P G 上最小的弧容量。 证明：显然。 定理 9.3..2 设 * f 是网络 N 中的最大流，f 是 N 中的一个可行流，则增量网络 N ( f )中的最大流的流值为 * Val f Val f − 。 证明：考虑 N ( f )中的任一个割 (, ) S S ， 对 ∀ ∈ (,) (, ) uv SS ，要么 c uv f vu ′(,) (, ) = ；要么 c uv cuv f uv ′(,) (,) (,) = − 【见注 (1)】。 令： {( , ) ( , ) | ( , ) ( , )} A1 =∈ = uv SS c uv f vu ′ ， {( , ) ( , ) | ( , ) ( , ) ( , )} A uv SS c uv cuv f uv 2 =∈ = − ′ 则 A A 1 2 ∩ = φ 且 ( ) A A Af 1 2 ∪ = 。 故 (,)( , ) (, ) (,) uv SS Cap S S c u v ∈ ′ ′ = ∑ = (,) (,) (,) (,) 1 2 uv A uv A c uv c uv ∈ ∈ ∑ ∑ ′ ′ + (,) (,) ( , ) ( ( , ) ( , )) 1 2 uv A uv A f vu cuv f uv ∈ ∈ =+− ∑ ∑ (,) (,) (,) (, ) (, ) (, ) 21 2 uv A uv A uv A cuv f vu f uv ∈∈ ∈ =+ − ∑∑ ∑ = Cap S S ( , ） f () () S fS − + + − = − Cap S S Val f (, ) 。 当 f 给定后 min ( , ) min ( , ) C ap S S Cap S S Val f ′ = − 。由最大流最小割定理， * * Val f Val f Val f = −  . 其中 * f  表示 N f ( ) 中的最大流。 二、网络顶点的分层： 设网络 N = (V, x, y, A, C)，令： { | V vV i = ∈ x 到 v 的最短有向路的长为 i}。设 x 到 y 的最短有向路 的长为 n，则 (1) , 0 n x ∈ ∈ V yV ；(2) V V i j ∩ = φ ，( ) j i ≠ 。Vi 中的顶点称为网络 N 的第 i 层顶点。 注：这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路。 例： { }, { , }, { , , , } 0 1 12 2 3 4 5 V xV vv V v v v y = = = S S u v u v u v u v N N(f) 非零非饱和弧 饱和弧 零流弧 非零非饱和弧 S S u v u v u v u v ∈A1 ∈A1 ∈A2 ∈A2 网络 N 网络 N 的分层。 v1 x y v3 v2 v4 v5 v1 x y v3 v2 v4 v5