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

【さいだいふろーさいしょうかっとていり (maximum flow minimum cut theorem)】

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