ネットワークフロー電卓最大フロー

ネットワークフロー電卓最大フロー

ネットワークフロー電卓最大フローは、任意の容量付き有向ネットワークにおいて、選択した始点（ソース）s から終点（シンク）t への最大フローを計算します。内部では幅優先探索による増加道を用いた Ford-Fulkerson 法（Edmonds-Karp アルゴリズム）を実行し、見つかったすべてのパスを記録します。これにより、意思決定プロセスを1回ずつの反復でリプレイして確認できます。また、結果ページには最小カット（フロー値が真に最適であることを証明するボトルネックの分割）も表示されます。

最大フロー問題とは？

フローネットワークとは、有向グラフ G = (V, E) と容量関数 c: E → ℝ_≥0 の組み合わせです。2つの頂点が区別されます：フローが湧き出すソース s と、フローが吸収されるシンク t です。フロー f は、以下の規則に従うエッジへの値 f(u, v) ≥ 0 の割り当てです：

最大フロー問題は、このフロー値 |f| を最大化するフロー f を求めるものです。直感的に言えば、エッジが所定の容量を持つ水道管であるとき、s から t へ毎秒何リットルの水を送れるかという問題です。

アルゴリズムの仕組み — BFS を用いた Ford-Fulkerson

このアルゴリズムは、現在のフローと並行して残余グラフを保持します。容量 c、現在のフロー f の各エッジ (u, v) に対して、残余グラフには以下が含まれます：

• 順方向残余エッジ (u, v)：容量は c − f（あとどれだけ流せるか）
• 逆方向残余エッジ (v, u)：容量は f（確定したフローをどれだけキャンセルできるか）

各反復において、残余グラフ上で s から t への幅優先探索（BFS）を実行します。パスが見つかった場合、そのパス上の最小のエッジ容量（ボトルネック）を、パスに沿った各順方向エッジのフローに加え、逆方向エッジのフローから差し引きます。これを増加道と呼びます。BFS で t に到達できなくなったとき、現在のフローが最適となります。

（任意のパス選択ではなく）BFS を使用することで、Ford-Fulkerson 法は Edmonds-Karp アルゴリズムとなり、実行時間は O(V · E²) に抑えられることが保証されます。また、通常の Ford-Fulkerson では対応できない無理数の容量に対しても、必ず終了することが保証されます。

最大フロー最小カット定理

カットとは、頂点集合を s ∈ S かつ t ∈ T となる2つの集合 (S, T) に分割することです。その容量は、S から T へ向かうエッジの容量の合計です：

最大フロー最小カット定理 (Ford & Fulkerson, 1956) によれば：

このツールは最小カットを自動的に検出します。Edmonds-Karp が終了した後、残余グラフ上で s からもう一度 BFS を実行します。到達できた頂点が S を構成し、残りが T となります。元のグラフで S → T を横断するすべてのエッジは飽和しており、それらの容量の合計は最大フロー値と正確に一致します。これは結果の「最小カット容量 ✓ 最適性が確認されました」として表示されます。

学習のための機能

• ステップバイステップのアニメーション: 再生、一時停止、ステップ制御により、すべての増加道をリプレイできます。BFS がどのパスを選んだか、どのエッジがボトルネックだったか、合計フローがどのように増えていったかを確認できます。
• 3つの同期行列: 容量行列 C、最終フロー行列 f、残余行列 C − f を切り替えて表示できます。これら3つの図を合わせることで、フローの全容を把握できます。
• 最小カット分割ビュー: S側と T側の頂点をチップ形式でリスト表示し、境界にある飽和エッジを赤色で強調します。
• エッジごとのテーブル: すべてのエッジについて、容量、フロー、残余、利用率バー、飽和状態を表示します。
• 左から右へのレイヤードレイアウト: ソースからの BFS 距離に基づいてグラフを描画するため、水が左から右へ「流れる」ように見えます。これは教科書でよく使われる描画スタイルです。

入力形式

1. 容量付きエッジリスト

1行に1つのエッジを入力します。矢印形式が最も読みやすいですが、いくつかの代替形式も可能です：

他にも A, B, 10 ・ A B 10 ・ A -> B , 10 などが受け付けられます。同じペアの間に複数のエッジがある場合は合算されます。

2. 容量行列

1行に1行ずつ、スペースまたはカンマで区切った値を入力します。項目 C[i][j] は頂点 i から 頂点 j へのエッジの容量です。エッジがない場合は 0 を使用してください。行列は正方行列である必要があり、対角成分は 0（自己ループなし）である必要があります。

行列ラベルフィールドに、対応する頂点ラベルを（カンマまたはスペース区切りで）入力してください。省略した場合、ラベルはデフォルトで S, A, B, …, T になります。

最大フローの応用例

実行例

「教科書」のクイック例は、ソース S とシンク T を持つ6ノードのネットワークです。Edmonds-Karp を実行すると、4つの増加道が見つかります：

1. S → A → B → T：ボトルネック 4（エッジ A-B が制限）。累積フロー: 4。
2. S → A → D → T：ボトルネック 6。累積フロー: 10。
3. S → C → D → T：ボトルネック 4（エッジ D-T が制限、残り 4）。累積フロー: 14。
4. S → C → D → B → T：ボトルネック 5。累積フロー: 19。

これ以上増加道が存在しないため、アルゴリズムは停止します。最小カットは (S = {S, C}, T = {A, B, D, T}) であり、境界エッジは S → A (容量 10) と C → D (容量 9) です。これらを合計すると 19 となり、最大フロー値と一致します。

この電卓の使い方

1. タブを使用して入力形式を選択します（エッジリスト推奨、または容量行列）。
2. ネットワークを入力します。 クイック例から開始して変更することもできます。行列入力の場合、S, A, B, …, T 以外の名前を使いたい場合はラベルも入力してください。
3. ソースとシンクを指定します（空欄にすると S と T を自動検出します）。
4. 最大フローを計算をクリック。 結果ページに最大フロー値、最小カット分割、レイヤードグラフ可視化、すべての増加道、エッジ利用率テーブル、および3つの行列（容量、フロー、残余）が表示されます。
5. グラフの下にあるアニメーションを再生して、アルゴリズムの決定プロセスを確認します。任意の増加道のステップをクリックすると、その時点へ直接ジャンプできます。

制限事項

• 頂点数: 最大30まで（可視化と行列の読みやすさを維持するため）。
• エッジ数: 最大200まで。
• 容量: 非負、10⁹ まで。小数の容量も可能です。
• 自己ループ不可: 標準的な最大フローの定式化において自己ループはフローを運ばないため、除外されます。

よくある質問

最大フロー問題とは何ですか？

各エッジに非負の容量がある有向ネットワークにおいて、指定された始点（ソース）s から終点（シンク）t へ、各エッジのフローがその容量を超えず、かつソースとシンク以外の各頂点に流入するフローと流出するフローが等しいという規則に従って、どれだけのフローを送り出せるかを問う問題です。その答えを最大フロー値と呼びます。

Ford-Fulkerson 法とは何ですか？

Ford-Fulkerson は最大フローを計算するための一般的な手法です。残余グラフ内でソースからシンクへの増加道を繰り返し見つけ、そのパスに沿って可能な限りのフロー（ボトルネック容量）を押し出し、残余グラフを更新します。増加道が存在しなくなった時点で処理は終了します。パスの選択に幅優先探索（BFS）を使用する場合、それは Edmonds-Karp アルゴリズムと呼ばれ、O(V · E²) の時間で動作します。

フローネットワークの最小カットとは何ですか？

カットとは、頂点をソースを含む集合 S とシンクを含む集合 T の2つに分割することです。カットの容量は、S から T へのエッジの容量の合計です。最小カットとは、最小の容量を持つカットのことです。有名な最大フロー最小カット定理は、最大フロー値が常に最小カット容量と等しいことを証明しており、一方を見つければもう一方も自動的に得られます。

残余グラフとは何ですか？

残余グラフは、各エッジにあとどれだけフローを流せるかを追跡するものです。容量 c、現在のフロー f の元のエッジ (u, v) に対して、残余グラフには容量 c - f の順方向エッジ (u, v)（残りの容量）と、容量 f の逆方向エッジ (v, u)（キャンセル可能なフロー）が含まれます。増加道は残余グラフのエッジを使用するため、アルゴリズムは以前の決定を取り消すことができます。

なぜこのツールは増加道に BFS を使用するのですか？

幅優先探索（Edmonds-Karp）で増加道を選択することで、エッジの容量に関係なく多項式時間での終了が保証されます。任意のパス選択戦略を用いる通常の Ford-Fulkerson では、特殊な入力に対して指数関数的な反復回数ループしたり、無理数の容量に対して終了しなかったりすることがあります。また、BFS は最短の増加道を生成するため、読みやすく理解しやすくなります。

飽和したエッジとはどういう意味ですか？

エッジのフローがその容量と等しくなり、それ以上フローを流せなくなった状態を「飽和」と呼びます。飽和したエッジはネットワークのボトルネックであり、すべての最小カットは、カットの S 側から T 側に向かう飽和エッジのみで構成されます。ツールでは飽和エッジを赤色でハイライトし、ボトルネックの構造を一目で確認できるようにしています。

参考文献

• 最大フロー問題 — Wikipedia
• フォード・ファルカーソンのアルゴリズム — Wikipedia
• エドモンズ・カープのアルゴリズム — Wikipedia
• 最大フロー最小カット定理 — Wikipedia