グラフの最大流・最小カット
バグ・不具合を報告
有向ネットワークにおける始点から終点への最大通過量と制約となる切断集合を調べる。
容量・流量は利用者が統一した単位で入力してください。0容量の辺も扱います。最大流が0でも、グラフに増加路がなければ正常な計算結果です。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は3項目です。
計算結果
—
- 最小カット容量
- —
- カット辺の数
- —本
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
各有向辺eの容量c(e)≥0に対し、0≤f(e)≤c(e)、始点と終点以外の各ノードでは流入量=流出量とします。残余容量が正の辺だけを通る最短増加路を幅優先探索し、経路の最小残余容量だけ流量を増やします。増加路がなくなったときの総流量が最大流Fです。始点sから残余容量が正の辺を通って到達できる集合Sとその他Tの間で、S→Tの容量合計C(S,T)=Σc(u,v)が最小カット容量で、F=C(S,T)です。内部計算は容量を10⁶倍した安全整数で行い、小数第6位まで厳密に扱います。
最大流、最小カット容量、入力辺ごとの流量・未使用容量、カット辺とノード分割。
計算例(架空の数値)
例:s→a容量3、s→b容量2、a→t容量2、b→t容量2、a→b容量1なら最大流は4。カット辺はa→t(2)とb→t(2)で、容量合計も4です。
適用対象と限界
容量が有限かつ0以上の単一始点・単一終点を持つ有向グラフ。費用最小化、需要供給の輸送費計画、多始点多終点、容量下限、無限容量、自己ループ、時間変動容量は対象外です。。
方法と出典
方法:E485-Edmonds–Karp fixed-6 v1.0(2026-11-13)。データ記録日:2026-11-13。