グラフの最大流・最小カット

有向ネットワークにおける始点から終点への最大通過量と制約となる切断集合を調べる。

容量・流量は利用者が統一した単位で入力してください。0容量の辺も扱います。最大流が0でも、グラフに増加路がなければ正常な計算結果です。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は3項目です。

ノード必須
行ノードID操作
1
2

1列を左端の欄へタブ区切りで貼り付けられます。60行まで。

半角英数字で始まるID。最大60ノード。ノード名は大文字・小文字を区別します。

有向辺と容量任意
行出発ID到着ID容量(共通単位)操作
1
2

3列を左端の欄へタブ区切りで貼り付けられます。200行まで。

出発→到着の向きを区別します。容量は同じ単位の0~100万、小数第6位まで。最大200辺。並行辺も別行で入力できます。

ノード表に登録したIDを入力してください。

始点とは異なるノード表のIDを入力してください。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

各有向辺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。