フローまたはマッチングの問い合わせを実行する方法
- 01ネットワークを構築します。Flow network S→T プリセットは 6 ノードの有向ネットワークです。二部判定は Bipartite K₃,₃ プリセットと任意のグリッドも受け付けます。
- 02Dinic max-flow または Edmonds–Karp を選び、Source S と Sink T を設定して、最大流、最小カット容量、照合行、辺ごとのフロー/容量テーブルを読みます。
- 03Bipartite checkでは判定、左集合と右集合、そして答えが No のときは奇数長閉路の証拠を読みます。
- 04Hungarian matchingでは二部グラフを読み込み、マッチングの大きさ、ペア、最小頂点被覆、未マッチの頂点を読みます。
- 05実行をステップ実行して、増加路がフロー値を押し上げる様子を確認します。
計算例
| 設定 |
計算結果 |
| フロープリセット、Dinic S → T |
最大流 19、最小カット容量 19、照合(Edmonds–Karp)19、カット辺 S→A, B→D、ソース側 S, B |
| フロープリセット、辺ごとのフロー |
S→A 10/10、S→B 9/10、A→C 4/4、A→D 6/8、B→D 9/9、C→T 9/10、D→C 5/6、D→T 10/10 |
| Bipartite K₃,₃、Hungarian matching |
最大マッチング 3、ペア L1–R3, L2–R2, L3–R1、最小頂点被覆 L1, L2, L3、未マッチ — |
| Cycle C₅、Bipartite check |
二部 No、奇数長閉路の証拠 C → B → A → E → D → C |
| Grid 4 × 5、Bipartite check |
二部 Yes、左 10 ノード(1-1, 1-3, 1-5, 2-2 から)、右 10 ノード(1-2, 1-4, 2-1 から) |
2 つのフローアルゴリズムは 19 で一致し、カット辺が上界を裏付けます。S→A が 10、B→D が 9 を運び、合計が最大流です。シンクは C→T 経由で 9、D→T 経由で 10 を受け取り、やはり 19 になります。
なぜカットがフローを証明するのか
最大流最小カットは、最良のフローが最も安いボトルネックに等しいと述べます。Dinic は増加路が残らなくなると停止し、パネルはそのとき S からまだ到達できるノード — ソース側 S, B — と、そこを離れる辺 S→A と B→D を表示します。その容量 10 と 9 を足すとフローになります。どの単位もこのカットを横切らなければならないので、これより大きいフローは存在しません。マッチング側では、Kőnig の定理が同じ形式の証明を与えます。大きさ 3 のマッチングと大きさ 3 の頂点被覆が互いを固定します。
限界
- マッチングには二部グラフが必要です。
- Petersen プリセットで Hungarian matching を実行すると、パネルは部分的な答えを返さず、"Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply" と拒否します。一般グラフのマッチングは提供されません。
- 一度に 1 組のソース・シンク、コストなし。
- min-cost flow、多品種フロー、辺の下限制約はありません。組ごとに順番に実行し、ソース側を比較してください。
- できないこと。
- 報告された最小カットを超えてカットを列挙することはなく、ネットワークファイルもインポートしません。ネットワークをキャンバス上で構築し、隣接行列を math tools に持っていくか、Components で到達可能性を一覧してください。
方向の落とし穴
カット辺は有向ペアとして表示されます。有向の Flow プリセットでは S→A と B→D です。無向の既定グラフでは、Dinic A→F が A→B, A→C をソース側 A として出力します。ソース側は実行をまたいで安定した読み値 — アルゴリズムが停止したときに S からまだ到達できるものすべて — なので、手作業でカットを再確認するときは、矢印の向きではなくその行を比較してください。
活用場面
容量計画
フロープリセットは、19 単位の需要のうちどれだけが通過できるか、ボトルネックがどこにあるかを示します。S→B は 1 単位の余裕を保ち、A→D は 2 を残しますが、カット S→A / B→D は飽和しています。カット辺の容量を上げればフロー値は動き、ネットワーク内部の辺を上げても通常は動きません。
割り当て問題
Bipartite K₃,₃ では、Hungarian パネルが左の 3 ノードすべてをペアにし、同じ大きさの被覆を出力するので、割り当ては証明可能な最大値です。グリッドは二部判定に Yes と答え、10/10 の等しい分割を示します。一方 C₅ は No と答えて奇数長閉路を返します — 2 彩色が存在しないことの証明書です。Traversal パネルを使えば、色のグループをノードごとに表示できます。
プライバシー
フロー、彩色、マッチングの計算はすべてブラウザ内で実行され、何もアップロードされません。
参考文献
- Wikipedia, Maximum flow problem, en.wikipedia.org (访问日期:2026-10-07)— 増加路とフロー値。
- Wikipedia, Max-flow min-cut theorem, en.wikipedia.org (访问日期:2026-10-07)— フローとカット容量の一致。
- Wikipedia, Bipartite graph, en.wikipedia.org (访问日期:2026-10-07)— 2 彩色と奇数長閉路。
- Wikipedia, Maximum cardinality matching, en.wikipedia.org (访问日期:2026-10-07)— 増加路によるマッチング。
- Wikipedia, Kőnig's theorem (graph theory), en.wikipedia.org (访问日期:2026-10-07)— 二部グラフでマッチングと頂点被覆が一致。
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
- Updated