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

OR事典

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

読み方：さいだいふろーさいしょうかっとていり
【英】：maximum flow minimum cut theorem

枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理.

「OR事典」の他の用語

グラフ･ネットワーク：

平面グラフ  循環フロー  最大フローアルゴリズム  最大フロー最小カット定理  最大マッチング最小被覆定理  最小木問題  最小費用フロー問題

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（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