证明:令∫=f+∫。对N的任何割(S,S), ra疒=f"(s)-f(S)=∑f(un)-∑f(u 2((u,v)+f(u, v)-f'(v, u)-2((u,v)+f(u,v)-f'(v, u) f(u, v) f(u, v) ·\零流弧 ------ y非零非饱和弧 f(x)+∑f(2 饱和弧 (,v)e(S,S) 零流弧 非零非饱和弧 f(u,v) -/饱和弧 (u, TE(S,S (u, ve(s, s) NO =lal∫+lal∫"(S)-∫(S)=lal∫+lalf'。 w()=∑f(n,y)n() =∑(f(u1)+f(un)-f(,)() (a,T)∈A ∑f(un)w(u)+∑f(uv)m(u)+∑f(n,u),(-m(uv) (a,T)∈A (a,v)∈A =w()+w(f’) 引理942设∫和∫是N中两个可行流,则N()中必存在可行流∫",满足∫”=f+f 证明:利用∫和来定义N(f)中一个流∫如下 对V(u,v)∈A, 若∫(u,v)≥f(u,v),则定义f(u,v)=f(,v)-f(u,v),且f(v,u)=0 若∫(u,y)<f(u,v),则定义f(,v)=0且f(v,u)=f(l,v)-f'(l,v) →γ→ 易验证这样定义的∫"是N(f)中的一个可行流,且∫'=f+∫"。证毕。 例: ∫=4 l(1 0(2) 0(4) N中两个可行流f和,括号中是弧容量N/)及其一个可行流∫’,括号中是弧容量 引理943设G是一个有向图。如果G中每个顶点都至少有一条出弧,则G包含一个有向圈 证明(略)。证明：令 * f = + f f  ′。对 N 的任何割(, ) S S ， ** * * * (,)( , ) (,)( , ) (,)( , ) (,)( ,) () () (,) (,) ( ( , ) ( , ) ( , )) ( ( , ) ( , ) ( , )) uv SS uv S S uv SS uv S S Val f f S f S f u v f u v f uv f uv f vu f uv f uv f vu + − ∈ ∈ ∈ ∈ =−= − = +− − +− ′′ ′′ ∑ ∑ ∑ ∑ (,)( , ) (,)( ,) (,)( , ) (,)( ,) (,)( , ) (,)( , ) (,) (,) (, ) (, ) (, ) (,) uv SS uv S S uv SS uv S S uv SS uv S S f uv f uv f uv f vu f vu f uv ∈ ∈ ∈ ∈ ∈ ∈ ⎛ ⎞ = − ⎜ ⎟ ⎝ ⎠ ⎛ ⎞ + + ′ ′ ⎜ ⎟ ⎝ ⎠ ⎛ ⎞ − + ′ ′ ⎜ ⎟ ⎝ ⎠ ∑ ∑ ∑ ∑ ∑ ∑ Val f Val f S f S Val f Val f () () + − =+ − =+ ′′ ′。 ( ) * * (,) (,) (,) (,) (,) ( ) (,) (,) (,) (,) (, ) (, ) ( , ) ( , ) ( , ) ( , ) ( , ) ( ( , )) () ( ) uv A uv A uv A uv A uv A w f f uv wuv f uv f uv f vu wuv f uv wuv f uv wuv f vu wuv wf w f ∈ ∈ ∈∈ ∈ = ⋅ = +− ⋅ ′ ′ = ⋅ + ⋅ + ⋅− ′ = + ′ ′ ∑ ∑ ∑∑ ∑ 引理 9.4.2 设 f 和 * f 是 N 中两个可行流，则 N f ( ) 中必存在可行流 f ′，满足 * f = + f f  ′。 证明：利用 f 和 * f 来定义 N f ( ) 中一个流 f ′如下： 对∀ ∈ (,) uv A， 若 * f (,) (,) uv f uv ≥ ，则定义 * f ′(,) (,) (,) uv f uv f uv = − ，且 f vu ′(, ) 0 = ； 若 * f (,) (,) uv f uv < ，则定义 f uv ′(,) 0 = 且 * f ′(, ) (,) (, ) vu f uv f uv = − 。 f f * u v ⎯⎯⎯→≥ ⇒ ； f f * u v ⎯⎯⎯→< ⇒ 易验证这样定义的 f ′是 N f ( ) 中的一个可行流，且 * f = f f + ′。证毕。 例： 引理 9.4.3 设 G 是一个有向图。如果 G 中每个顶点都至少有一条出弧，则 G 包含一个有向圈。 证明(略)。 f * − f 0 u v 0 f − f * u v S S u u v u v u v v u v u v S S u u v u v u v v u v u v N(f) N 零流弧 非零非饱和弧 饱和弧 零流弧 非零非饱和弧 饱和弧 f = 4 f * = 4 (5) f (2) = 2 f * =1 (3) f = 2 f * = 3 1(1) 0(2) 0(1) 0(4) 1(2) 0(0) N 中两个可行流 f 和 f * ，括号中是弧容量 N( f )及其一个可行流 f ′ ，括号中是弧容量