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

OR事典

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

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

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

「OR事典」の他の用語

グラフ･ネットワーク：

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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 08:27 UTC 版)

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

定義

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

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

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

右図はノード $V=\{s,o,p,q,r,t\}$ カテゴリ / コモンズ