最大フロー問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
最大フローのあるフローネットワークの例。始点 s と終点 t があり、各枝の数値はフローと容量を示す。

最大フロー問題または最大流問題: Maximum flow problem)とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である[1]。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である循環流問題の特殊ケースと見ることもできる。

最小カット問題: Minimum cut problem)とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。

2部グラフの最大マッチング問題: Maximum bipartite matching)とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける[1]

解法[編集]

有向グラフ G(V,E) において、各枝 u,v の容量を c(u,v) としたとき、始点 s から終点 t への最大フロー f を求める。この問題の解法アルゴリズムは多数存在する。

発表年 名称 計算量 説明
線形計画法 正規フローの定義から制約条件が与えられる。\sum_{v \in V} f(s,v) を最適化
1956年 フォード・ファルカーソンのアルゴリズム O(E \cdot \text{maxflow}) 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。
1970年 エドモンズ・カープのアルゴリズム O(VE^2) フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。
1970年 Dinic法 O(V^2 E) ステップ毎に残余グラフについて幅優先探索で層別グラフを構築する。層別グラフでの最大フローは O(VE) で求められ、ステップの反復は最大 n-1 回である。
1978年 MPM法[2] O(V^3) Malhotra, Pramodh-Kumar, Maheshwari が発表
1981年 動的木を使ったDinic法[3] O(VE \log V) 層別グラフの最大フロー計算を動的木を使うことで O(E \log V) で行う。
1986年 汎用プッシュ再ラベル法[4] O(V^2E) プリフロー(頂点群で超過する可能性のあるフロー関数)を使うアルゴリズム。正の超過のある頂点(グラフ内のアクティブな頂点)がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。
1986年 FIFO式頂点選択規則付きプッシュ再ラベル法[4] O(V^3) 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。
1986年 動的木を使ったプッシュ再ラベル法[4] O(V^2\log(V^2/E)) height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。
1994年 KRT (King, Rao, Tarjan) 法[5] O(EV \log_{E/V \log V}V)
1998年 バイナリブロッキングフロー法[6] O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U}) 計算量のUはネットワークの最大容量。
2013年 Jim Orlin法 + KRT (King, Rao, Tarjan) 法[7] O(VE) Jim Orlin法自体はO(VE + E^{31/16} \log^2 V)だが、KRT法を組み合わせることでO(VE)になる。

これら以外にも解法アルゴリズムは多数存在し、参考文献(特に Goldberg and Tarjan 1988)を参照されたい。

脚注・出典[編集]

  1. ^ a b T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン 『アルゴリズムイントロダクション』 近代科学社、2013年12月17日(原著2009年7月31日)、第3版(日本語)。ISBN 476490408X
  2. ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An O(|V|^3) algorithm for finding maximum flows in networks". Information Processing Letters 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.  編集
  3. ^ Daniel Dominic Kaplan Sleator. An o(nm log n) algorithm for maximum network flow. 
  4. ^ a b c Goldberg, A. V.; Tarjan, R. E. (1986). "A new approach to the maximum flow problem". STOC '86 Proceedings of the eighteenth annual ACM symposium on Theory of computing: 136–146. doi:10.1145/12130.12144.  編集
  5. ^ King, V.; Rao, S.; Tarjan, R. (1994). "A Faster Deterministic Maximum Flow Algorithm". Journal of Algorithms 17 (3): 447–474. doi:10.1006/jagm.1994.1044.  編集
  6. ^ Goldberg, A. V.; Rao, S. (1998). "Beyond the flow decomposition barrier". Journal of the ACM 45 (5): 783. doi:10.1145/290179.290181.  編集
  7. ^ Orlin, James B. (2013). "Max flows in O(nm) time, or better". STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing: 765–774. doi:10.1145/2488608.2488705.  編集

参考文献[編集]