OR事典

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

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

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

「OR事典」の他の用語

グラフ･ネットワーク：

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