蟻本P191 最大流 - 最小カット定理

蟻本に載ってることそのまま書くだけ
蟻本の最大流で使われたグラフをそのままサンプルで使います。
↓↓

グラフのカットとは、ある頂点集合Sに対して、Sから出ていく辺の集合の事をいい、
カット(S V/S)のように表します。また、その辺の容量の和をカットの容量といいます。

さらに、Sの中にsを、V/Sの中にtを含むようにカットすることを、
s-tカットといいます。

最小カット問題とは・・・
ネットワークにに対して、sからtへのパスが存在しなくなるために（つまりs-tカットで）
除去しなければいけない辺の容量の和の最小値はどれだけか
という問題である。

フロー流量とカット容量の関係

まず、任意のs-tフロー f と任意のs-tカット(S, V/S)を考えてみましょう。

↓こんなフローとカット↓

sについては( fの流量 ) = ( sから出る辺の流量 )であり、
それ以外のSの頂点vについては( vから出る辺の流量 = vに入る辺の流量 )であるので、

( fの流量 ) = ( Sから出る辺の流量 ) - ( Sに入る辺の流量 ) となります。

ここで、辺に流す量は、どう頑張っても容量を超えることはできません。
カットの容量は、Sから出て行く辺の容量の和となりますので、

( fの流量 ) <= ( カットの容量 )となる事がわかります。

Ford-Fulkersonのアルゴリズムの正当性

次に、Ford-Fulkersonのアルゴリズムによって得られたフローFを考えて見ましょう

フローFに対する残余グラフにおいて

s-vパスの存在するような頂点vからなる集合をSとすると、

Fの残余グラフにおいて、s-tパスが存在しない事により(Sに頂点tは含まれないので)、
(S, V/S)はs-tカットとなります。

また、Sの定義により、カットに含まれる辺e（Sから出て行く辺）について、
F(e) = c(e) （容量いっぱいいっぱい）となっており、
V/S から S に向かう辺e（Sに入ってくる辺）について、
F(e) = 0 となっています。

したがって、
( Fの流量 ) = ( Sから出る辺の流量 ) - ( Sに入る辺の流量 ) = ( カットの容量 ) 
となり、
先ほどの不等号( fの流量　<= カットの容量 )から、Fが最大流であることが分かります。

Ford-Fulkersonのアルゴリズムを使うと、
( Fの流量 ) = ( カットの容量 )となるs-tカットが必ずできるため、
( fの流量 ) <= ( カットの容量 )より、
このs-tカットが最小カットであることも分かります。