最大フロー最小カット定理（さいだいフローさいしょうカットていり、）は、フローネットワークにおいて最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。二端子フローネットワーク formula_1 が与えられたとする。つまり、有限の有向グラフformula_2 の各エッジ（辺）formula_3 に非負実数の容量 formula_4が割り当てられており、始点となるノード（入口）formula_5 と、終点となるノード（出口）formula_6 が指定されたとする。フロー の流量 とは、入口 から出て行くフローの合計である。このネットワーク のカット とは、ノード（頂点） を2つの集合 formula_8 と formula_9 に分割し、formula_8 には formula_5 が含まれ、formula_9 には formula_6 が含まれるようにすることをいう。この定理は1956年、P. Elias、A. Feinstein、クロード・シャノンによって証明された。また、L.R. Ford, Jr. と D.R. Fulkerson も同じ年に独自に証明した。最大フローを求める問題は線形計画問題の特殊形式であり、最大フロー最小カット定理は線形計画の双対性定理の特殊ケースと見ることもできる。

出典:wikipedia