最大フロー最小カット定理

最大フロー最小カット定理（さいだいフローさいしょうカットていり、テンプレート:Lang-en-short）は、フローネットワークにおける最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。

定義

左から:1. 与えられたネットワーク。各エッジの容量はすべて等しいとする。2. ひとつのフロー。3. 2の残余ネットワークと、その増加道。 4. 最大フローの残余ネットワーク。s から到達可能な緑の丸印のノードの集合をS, 不可能な青の四角のノードの集合をTとすると、(S, T) が最小カットになっている。

二端子フローネットワーク $\mathrm{N}=(G(V,E),c,s,t)$ が与えられたとする。つまり、有限の有向グラフ$G(V,E)$ の各エッジ（辺）$(u,v)$ に非負実数の容量 $c(u,v)$が割り当てられており、始点となるノード（入口）$s$ と、終点となるノード（出口）$t$ が指定されたとする。

フロー テンプレート:Mvar の流量 テンプレート:Math とは、入口 テンプレート:Mvar から出て行くフローの合計である。

$|f|=\sum _{v\in N^{-}(s)}f(s,v)$

このネットワーク テンプレート:Mvar のカット テンプレート:Math とは、ノード（頂点）テンプレート:Mvar を2つの集合 $S$ と $T$ に分割し、$S$ には $s$ が含まれ、$T$ には $t$ が含まれるようにすることをいう。

テンプレート:Mvar と テンプレート:Mvar 以外は自由にどちらかの集合に属することができるので、可能なカットの種類は

$2^{|V|-2}$

個ある。

カット $(S,T)$ の容量 テンプレート:Math とは、テンプレート:Mvar と テンプレート:Mvar の境界となっているエッジのうち、$S$ から $T$ に向かっているものの容量の合計である。

$c(S,T)=\sum _{u\in S,v\in T\mathrm{a}\mathrm{n}\mathrm{d}(u,v)\in E}c(u,v)$

フローでは流量が保存することから、あるフローが与えられている時、テンプレート:Mvar と テンプレート:Mvar の境界となっているエッジで、テンプレート:Mvar から テンプレート:Mvar へ流れる量から、テンプレート:Mvar から テンプレート:Mvar へ流れる量を引くと、フローの流量と等しくなる。

定理の主張

テンプレート:Mvarの最大フローとは、テンプレート:Mvarのフローのうち流量が最大のものをいい、最小カットとは、テンプレート:Mvarのカットのうち容量が最小のものをいう。このとき、最大フロー テンプレート:Math と 最小カット テンプレート:Mathについて、

$|f_{\mathrm{m}\mathrm{a}\mathrm{x}}|=c((S,T{)}_{\mathrm{m}\mathrm{i}\mathrm{n}})$

が成り立つ。

証明の概要

証明は、以下のようにしてできる。

最大フローはフォード・ファルカーソンのアルゴリズムにより、以下のようにして見つけることができる。

1. 二端子フローネットワーク テンプレート:Math が与えられたとする。
2. 最大フローを見つけるために、テンプレート:Mvar から テンプレート:Mvar への道を見つける。この道を構成するすべてのエッジの容量の最小値を、エッジの流量として割り当てると、これはこのネットワークのフローになる。
3. 流量の余裕を容量とする順方向のエッジと、現在の流量を容量とする逆方向のエッジからなるネットワークで、容量が 0 となるエッジを取り除いたものを残余ネットワーク (residual network) もしくは補助ネットワークと呼ぶ。この残余ネットワークの中で、同じように道を見つける。道の構成要素のうち、順方向のエッジでは流量を増加させ、逆方向のエッジでは流量を減少させることで、より流量の大きな新しいフローを得ることができる。（このような、フロー テンプレート:Mvar の残余ネットワークにおける テンプレート:Mvar から テンプレート:Mvar への道を、テンプレート:Mvar の増加道と呼ぶ。）
4. 増加道がなくなれば、このフローが テンプレート:Mvar の最大フローである。

最大フローの残余ネットワークは、$s$ から到達可能なノード群 $S$ と到達不可能なノード群 $T$ に分けることができる。増加道がないので、テンプレート:Mvar は テンプレート:Mvar に含まれる。定義より、残余ネットワーク上では テンプレート:Mvar から テンプレート:Mvar へのエッジは存在しない。もとのネットワークに戻って考えると、テンプレート:Mvar から出るエッジ テンプレート:Math はすべて、残余ネットワークに存在しないことから、流量の余裕がない、すなわち $f(u,v)=c(u,v)$ となっていることが分かる。また、テンプレート:Mvar に入るエッジは逆方向のエッジが残余ネットワークにないことから、流量が 0 であることが分かる。これらのことより、$c(S,T)=|f_{\mathrm{m}\mathrm{a}\mathrm{x}}|$となる。

したがって、$|f_{\mathrm{m}\mathrm{a}\mathrm{x}}|=c(S,T)\ge c((S,T{)}_{\mathrm{m}\mathrm{i}\mathrm{n}})$といえる。

次に $c((S,T{)}_{\mathrm{m}\mathrm{i}\mathrm{n}})\ge |f_{\mathrm{m}\mathrm{a}\mathrm{x}}|$ も成り立つことをみる。任意のフロー テンプレート:Mvar に対して、テンプレート:Mvar へ流れこむエッジ テンプレート:Math の流量は最大で テンプレート:Math であり、これの和は テンプレート:Math のカットの容量の定義そのものである。一方、テンプレート:Mvar から テンプレート:Mvar へ逆流するエッジの流量は、当然ながら最小値は 0 以上である。フローの流量は流量保存により、テンプレート:Mvar に流入する流量から逆流する流量を引いたものであることを確認したが、このことよりテンプレート:Mvarの流量は最大で カット テンプレート:Math の容量となる。このことより、$c(S,T)\ge |f|$、特に$c((S,T{)}_{\mathrm{m}\mathrm{i}\mathrm{n}})\ge |f_{\mathrm{m}\mathrm{a}\mathrm{x}}|$である。

例

最大フローのネットワーク。3つの最小カットがある。

右図はノード $V=\{s,o,p,q,r,t\}$ からなるネットワークであり、始点 $s$ から 終点 $t$ への総流量は 5 で、これがこのネットワークの最大である。

このネットワークには3つの最小カットが存在する。

カット	容量
$S=\{s,p\},T=\{o,q,r,t\}$	$c(s,o)+c(p,r)=3+2=5$
$S=\{s,o,p\},T=\{q,r,t\}$	$c(o,q)+c(p,r)=3+2=5$
$S=\{s,o,p,q,r\},T=\{t\}$	$c(q,t)+c(r,t)=2+3=5$

$(o,q)$ と $(r,t)$ が飽和しているにもかかわらず、$S=\{s,o,p,r\},T=\{q,t\}$ は最小カットではないことに注意されたい。これは残余ネットワーク（residual network） $G_f$ において、エッジ (r,q) の容量が $c_f(r,q)=c(r,q)-f(r,q)=0-(-1)=1$ であるためである。

歴史

この定理は1956年、P. Elias、A. Feinstein、クロード・シャノンによって証明された。また、L.R. Ford, Jr. と D.R. Fulkerson も同じ年に独自に証明した。最大フローを求める問題は線形計画問題の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理の特殊ケースと見ることもできる。

参考文献

• P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117--119, 1956.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 26: Maximum Flow, pp.643–700.
• テンプレート:Cite book

関連項目

• フォード・ファルカーソンのアルゴリズム
• 連結グラフ

外部リンク

• A review of current literature on computing maximum flows
• Max-Flow Min-Cut Animation
• Max-Flow Problem: Ford-Fulkerson Algorithm