最大フロー最小カット定理
【英】:maximum flow minimum cut theorem
枝容量をもつ有向グラフと入口, 出口となる2点が与えられているとき, 各枝の容量を超えず, 入口と出口以外では流出量と流入量が等しい枝上の流れに対し, 入口からの流入量をフロー値という. また, 入口を含み, 出口を含まないような点の部分集合から出る枝の容量の総和をカット値という. 最大フロー値が最小カット値に一致するというフォード(L. R. Ford, Jr.)とファルカーソン(D. R. Fulkerson)による定理.
グラフ・ネットワーク: | 平面グラフ 循環フロー 最大フローアルゴリズム 最大フロー最小カット定理 最大マッチング最小被覆定理 最小木問題 最小費用フロー問題 |
最大フロー最小カット定理
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/02/07 20:05 UTC 版)
最大フロー最小カット定理(さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem)は、フローネットワークにおける最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。
注釈
- ^ フローが整数値だけでなく、一般の実数値を取ることができる場合、このアルゴリズムは停止するとは限らない。しかし、最大フローが存在するとしたら、この方法により、より流量の大きな新しいフローを得ることはできないのであるから、そのフローの残余ネットワークは増加道を含まないということは言える。その場合、最大フローの存在については、一般の線形計画法の問題に還元するなどして示すことになる。
出典
- 1 最大フロー最小カット定理とは
- 2 最大フロー最小カット定理の概要
- 3 歴史
- 4 外部リンク
- 最大フロー最小カット定理のページへのリンク