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

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

定義

ファイル:Max-flow min-cut theorem.svg

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

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

フロー f の流量 | f | とは、入口 s から出て行くフローの合計である。

[math]|f| = \sum_{v \in N^-(s)} f(s, v)[/math]

このネットワーク Ν のカット (S, T) とは、ノード（頂点）V を2つの集合 [math]S[/math] と [math]T[/math] に分割し、[math]S[/math] には [math]s[/math] が含まれ、[math]T[/math] には [math]t[/math] が含まれるようにすることをいう。

s と t 以外は自由にどちらかの集合に属することができるので、可能なカットの種類は

[math]2^{|V|-2}\,[/math]

個ある。

カット [math](S,T)[/math] の容量 c(S, T) とは、S と T の境界となっているエッジのうち、[math]S[/math] から [math]T[/math] に向かっているものの容量の合計である。

[math]c(S,T) = \sum_{u \in S, v \in T \mathrm{and} (u, v) \in E} c(u, v)[/math]

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

証明の主張

Νの最大フローとは、Νのフローのうち流量が最大のものをいい、最小カットとは、Νのカットのうち容量が最小のものをいう。このとき、最大フロー fテンプレート:Msub と 最小カット (S, T)テンプレート:Msubについて、

[math]|f_{\mathrm{max}}| = c((S, T)_{\mathrm{min}})[/math]

が成り立つ。

証明の概要

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

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

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

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

したがって、[math]|f_{\mathrm{max}}| = c(S, T) \geq c((S, T)_{\mathrm{min}})[/math]といえる。

次に [math] c((S, T)_{\mathrm{min}}) \geq |f_{\mathrm{max}}|[/math] も成り立つことをみる。任意のフロー f に対して、T へ流れこむエッジ (u, v) の流量は最大で c(u, v) であり、これの和は (S, T) のカットの容量の定義そのものである。一方、T から S へ逆流するエッジの流量は、当然ながら最小値は 0 以上である。フローの流量は流量保存により、T に流入する流量から逆流する流量を引いたものであることを確認したが、このことよりfの流量は最大で カット (S, T) の容量となる。このことより、[math]c(S, T) \geq |f|[/math]、特に[math]c((S, T)_{\mathrm{min}}) \geq |f_{\mathrm{max}}|[/math]である。

例

ファイル:Max flow.svg

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

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

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

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

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

歴史

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

関連項目

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

外部リンク

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

参考文献

• 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.
• 藤重, 悟 『グラフ・ネットワーク・組み合せ論』 共立出版、2002年。ISBN 978-4320016170。