最大フロー問題

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

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

最小カット問題: Maximum 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) を最適化
フォード・ファルカーソンのアルゴリズム O(E \cdot \mathit{maxflow}) 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。
エドモンズ・カープのアルゴリズム O(VE^2) フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。
Dinic法 O(V^2 E) ステップ毎に残余グラフについて幅優先探索で層別グラフを構築する。層別グラフでの最大フローは O(VE) で求められ、ステップの反復は最大 n-1 回である。
汎用プッシュ再ラベル法 O(V^2E) プリフロー(頂点群で超過する可能性のあるフロー関数)を使うアルゴリズム。正の超過のある頂点(グラフ内のアクティブな頂点)がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。
FIFO式頂点選択規則付きプッシュ再ラベル法 O(V^3) 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。
動的木を使ったDinic法 O(VE\log(V)) 層別グラフの最大フロー計算を動的木構造を使うことで O(E\log(V)) で行う。
動的木を使ったプッシュ再ラベル法 O(V^2\log(V^2/E)) height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。

これら以外の解法については、参考文献(特に Goldberg and Tarjan 1988)を参照されたい。

脚注・出典[編集]

  1. ^ a b T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン 『アルゴリズムイントロダクション』 近代科学社、2013年12月17日(原著2009年7月31日)、第3版(日本語)。ISBN 476490408X

参考文献[編集]