最大フロー最小カット定理
(最大流最小カット定理 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/08/02 08:27 UTC 版)
最大フロー最小カット定理(さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem)は、フローネットワークにおける最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。
定義

二端子フローネットワーク
- 最大流最小カット定理のページへのリンク