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

最大フロー最小カット定理（さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem）は、フローネットワークにおける最大フロー問題と呼ばれる最適化問題に関する定理である。メンガーの定理から導出される。その内容は次の通り。

「最大フローは最小カットの容量に等しい」

平たく言えば、ネットワークの最大流量はボトルネックに左右されることを意味している。任意の2点間で、一方から他方へ流れる物量は、その経路内で最も弱い部分によって制限される。

定義

$G(V,E)$ が有限の有向グラフであり、各エッジ（枝） $(u,v)$ には容量 $c(u,v)$（非負実数）があるとする。さらに、始点となるノード $s$ と、終点となるノード $t$ を特に指定しておく。

カット（cut）とは、ノード群を2つの集合 $S$ と $T$ に分割し、$S$ には $s$ が含まれ、$T$ には $t$ が含まれるようにすることを言う。従って、可能なカットの種類は以下のようになる。

$2^{|V|-2}\,$

あるカット $(S,T)$ の容量とは、ネットワークを分断しているカットを表す線と交わっているエッジの容量の合計（ただし、$S$ から $T$ に向かっているもの）であり、次のように表される。

$c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v)$,

ここで以下の3つの条件は等価である。

1. $f$ は $G$ における最大フローである。
2. 残余ネットワーク（residual network）$G_f$ は増加道（augmenting path）を含まない。
3. あるカット $(S,T)$ について $|f| = c(S,T)$ が成り立つ。

証明の概要: もし増加道があれば、それを使ってより大きなフローを得ることができるため、最大フローとは呼べなくなるし、逆も成り立つ。増加道がない場合、残余ネットワーク内で $s$ から到達可能なノード群 $S$ と到達不可能なノード群 $T$ に分けることができる。すると、$c(S,T)$ は必ず 0 となる。さもなくば、$c(u,v) > 0$ であるようなエッジ $(u,v)$ が存在することになる。しかし、その場合 $v$ は $s$ から到達可能であり、$T$ に存在することは定義上あり得ない。

特にここから $\mathrm{max\ flow} \geq \mathrm{min\ cut}$ が証明される。なぜなら、最小カットは $\mathrm{max\ flow}$ に対応するカットと等しいかそれより小さいからである。

次に $\mathrm{min\ cut} \geq \mathrm{max\ flow}$ も成り立つ。グラフ $G$ のフローが $f$ であるとき、容量 $c$ のエッジ $(u, v)$ を取り除くと、その容量 $c$ を使えなくなるので、$f$ は少なくとも $f - c$ となる。しかしここで最小カット $c0$ でカットを跨ぐ全エッジを取り除くと、フローは $0$ となってしまう。最初のフローは $f$ であった。従って、任意のフロー $f$ について $f - c0 \leqq 0$ が成り立ち、特に $f$ が最大フローであってもそれは変わらない。従って、$f \leqq c0$ となる。

例

最大フローのネットワーク。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 も同じ年に独自に証明した。最大フローを求める問題は線形計画問題の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理の特殊ケースと見ることもできる。

関連項目

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

外部リンク

• 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.