最大フロー問題
提供: miniwiki
ファイル:Max flow.svg
最大フローのあるフローネットワークの例。始点 [math]s[/math] と終点 [math]t[/math] があり、各枝の数値はフローと容量を示す。
最大フロー問題または最大流問題（英: Maximum flow problem）とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である[1]。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。
最小カット問題（英: Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。
2部グラフの最大マッチング問題（英: Maximum bipartite matching）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける[1]。
解法
有向グラフ [math]G(V,E)[/math] において、各枝 [math]u,v[/math] の容量を [math]c(u,v)[/math] としたとき、始点 [math]s[/math] から終点 [math]t[/math] への最大フロー [math]f[/math] を求める。この問題の解法アルゴリズムは多数存在する。
| 発表年 | 名称 | 計算量 | 説明 |
|---|---|---|---|
| 線形計画法 | 正規フローの定義から制約条件が与えられる。[math]\sum_{v \in V} f(s,v)[/math] を最大化。 | ||
| 1956年 | フォード・ファルカーソンのアルゴリズム | [math]O(E \cdot \text{maxflow})[/math] | 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。 |
| 1970年 | エドモンズ・カープのアルゴリズム | [math]O(VE^2)[/math] | フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。 |
| 1970年 | Dinic法 | [math]O(V^2 E)[/math] | ステップ毎に残余グラフについて幅優先探索で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは [math]O(VE)[/math] で求められ、ステップの反復は最大 [math]n-1[/math] 回である。 |
| 1978年 | MPM法[2] | [math]O(V^3)[/math] | Malhotra, Pramodh-Kumar, Maheshwari が発表。 |
| 1981年 | 動的木を使ったDinic法[3] | [math]O(VE \log V)[/math] | 層別グラフのブロッキングフロー計算を動的木を使うことで [math]O(E \log V)[/math] で行う。 |
| 1986年 | 汎用プッシュ再ラベル法[4] | [math]O(V^2E)[/math] | プリフロー（頂点群で超過する可能性のあるフロー関数）を使うアルゴリズム。正の超過のある頂点（グラフ内のアクティブな頂点）がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。 |
| 1986年 | FIFO式頂点選択規則付きプッシュ再ラベル法[4] | [math]O(V^3)[/math] | 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。 |
| 1986年 | 動的木を使ったプッシュ再ラベル法[4] | [math]O(VE\log(V^2/E))[/math] | height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。 |
| 1994年 | KRT (King, Rao, Tarjan) 法[5] | [math]O(EV \log_{E/V \log V}V)[/math] | |
| 1998年 | バイナリブロッキングフロー法[6] | [math]O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})[/math] | 計算量のUはネットワークの最大容量。 |
| 2013年 | Jim Orlin法 + KRT (King, Rao, Tarjan) 法[7] | [math]O(VE)[/math] | Jim Orlin法自体は[math]O(VE + E^{31/16} \log^2 V)[/math]だが、KRT法を組み合わせることで[math]O(VE)[/math]になる。 |
これら以外にも解法アルゴリズムは多数存在し、参考文献（特に Goldberg and Tarjan 1988）を参照されたい。
脚注・出典
- ↑ 1.0 1.1 『アルゴリズムイントロダクション』 近代科学社、2013-12-17（原著2009-7-31）、第3版（日本語）。ISBN 476490408X。
- ↑ テンプレート:Cite doi
- ↑ Daniel Dominic Kaplan Sleator. An o(nm log n) algorithm for maximum network flow.
- ↑ 4.0 4.1 4.2 テンプレート:Cite doi
- ↑ テンプレート:Cite doi
- ↑ テンプレート:Cite doi
- ↑ テンプレート:Cite doi
参考文献
- Daniel D. Sleator and Robert E. Tarjan (1983). “A data structure for dynamic trees”. Journal of Computer and System Sciences 26 (3): 362–391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000.
- Daniel D. Sleator and Robert E. Tarjan (1985). “Self-adjusting binary search trees”. Journal of the ACM (New York, NY, USA: ACM Press) 32 (3): 652–686. doi:10.1145/3828.3835. ISSN 0004-5411.
- Andrew V. Goldberg and Robert E. Tarjan (1988). “A new approach to the maximum-flow problem”. Journal of the ACM (New York, NY, USA: ACM Press) 35 (4): 921–940. doi:10.1145/48014.61051. ISSN 0004-5411.
- Joseph Cheriyan and Kurt Mehlhorn (1999). “An analysis of the highest-level selection rule in the preflow-push max-flow algorithm”. Information Processing Letters 69 (5): 239–242. doi:10.1016/S0020-0190(99)00019-8.