Max-flow min-cut theorem

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/02/07 20:05 UTC 版)

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

定義

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

二端子フローネットワーク ${\displaystyle {\boldsymbol {\mathrm {N} }}=(G(V,E),c,s,t)}$

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

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

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

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

${\displaystyle (o,q)}$ と ${\displaystyle (r,t)}$ が飽和しているにも関わらず、${\displaystyle S=\{s,o,p,r\},T=\{q,t\}}$ は最小カットではないことに注意されたい。これは残余ネットワーク（residual network） ${\displaystyle G_{f}}$ において、エッジ (r,q) の容量が ${\displaystyle 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 も同じ年に独自に証明した。最大フローを求める問題は線形計画問題の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理の特殊ケースと見ることもできる。

脚注

注釈

1. ^ フローが整数値だけでなく、一般の実数値を取ることができる場合、このアルゴリズムは停止するとは限らない。しかし、最大フローが存在するとしたら、この方法により、より流量の大きな新しいフローを得ることはできないのであるから、そのフローの残余ネットワークは増加道を含まないということは言える。その場合、最大フローの存在については、一般の線形計画法の問題に還元するなどして示すことになる。

出典

1. ^ (藤重 2002, p. 54-59)

参考文献

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

関連項目

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

外部リンク

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