Document

1
アルゴリズムとデータ
構造
第１2回演習問題解説
2
補題１の証明
問題最大フロー最小カットの定理を証明せよ。
補題１任意のフローf、任意のカット(S,V-S)に対し、
F( f ) 
 f (u, v ) 
( u,v )E( S,V S )
 f (u, v )
---------------------------------①
( u,v )E( V S,S )
が成り立つ。ただし、F(f)はフローfの流量とし、E(S,T)=E∩(S×T)とする。
（証明） Sのサイズに関する数学的帰納法で証明する。
Sの要素数が１のとき、つまりS={s}のとき
 f (u, v ) 
( u,v )E( S,V S )
 f (u, v ) 
( u,v )E( V S,S )
 f (u, v )   f (u, v )  F(f )
( u,v )OUT ( s )
( u,v )IN( s )
となり、①が成り立つ。
Sの要素数がkのとき①が成り立つとする。
Sの要素数がk+1のとき
 f (u, v ) 
( u,v )E( S,V S )
 f (u, v ) 
( u,v )E( V S,S )

 f (u, v )   f (u , v ) 
( u,v )E( S  { u0 },V S )
 f (u, v ) 
( u,v )E( S  { u0 },V S )

vV S
0
( u,v )E ( V S,S  { u0 })
vV S
0
 f (u, v )   f (u , v )   f (v,u )
( u,v )E( V S,S  { u0 })
 f (u, v ) 
 f (u, v )   f (v,u )
vS  { u 0 }
0
vS  { u0 }
 f (u, v )
( u,v )E( S  { u0 },V ( S  { u0 })) ( u,v )E( V ( S  { u0 }),S  { u0 })
ただし、u0はS-{s}の任意の要素とする。よってSの要素数がk+1のときも成り立つ。 □
0
補題２とヒント
3
補題２ fが最大フロー⇔残余グラフにおいてsからtへの路が存在しない。
[最大フロー最小カットの定理の証明のヒント]
最大フローをf*、最小カットを(S*,V-S*)とし、最小カット値をC(S*,V-S*)とし
と
F( f *)  C(S*, V  S*)
F( f *)  C(S*, V  S*)
を示す。
また、補題２より、フローf*に対する残余グラフにおいてsから到達可能な頂点の集合
をS0とすれば、以下が成り立つことを使う。
c(u, v ) (u, v )  E(S0 , V  S0 )
f * (u, v )  
(u, v )  E( V  S0 , S0 )
 0
演習問題解答
4
（最大フロー最小カットの定理の証明）
最大フローをf*、最小カットを(S*,V-S*)とし、最小カット値をC(S*,V-S*)とする。
補題１より
F( f *) 
 f * (u, v ) 
( u,v )E( S *,V S *)
 f * (u, v ) 
( u,v )E( V S *,S *)
 c(u, v )  C(S*, V  S*)
( u,v )E( S *,V S *)
また、補題２より、フローf*に対する残余グラフにおいてsから到達可能な頂点の集合
をS0とすれば、以下が成り立つことが示せる。
c(u, v ) (u, v )  E(S0 , V  S0 )
f * (u, v )  
(u, v )  E( V  S0 , S0 )
 0
よって
F(f *) 
 f * (u, v) 
( u,v )E( S0 ,V S0 )
 f * (u, v) 
( u,v )E( V S0 ,S0 )
したがって、F(f*)=C(S*,V－S*)が成り立つ。
 c(u, v)  C(S*, V  S*)
( u,v )E( S0 ,V S0 )
□

Download Report