最大フロー問題

最大フローのあるフローネットワークの例。始点 $s$ と終点 $t$ があり、各枝の数値はフローと容量を示す。

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

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

脚注・出典

^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001年). “26”. Introduction to Algorithms (second edition ed.). MIT Press and McGraw-Hill. pp. 643–700. ISBN 0-262-53196-8

参考文献

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指定です. ISSN 0022-0000.
Daniel D. Sleator and Robert E. Tarjan (1985年). “Self-adjusting binary search trees”. Journal of the ACM (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 (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.

外部リンク

一般化最大フロー問題の多項式アルゴリズム野上裕介

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001年). “26”. Introduction to Algorithms (second edition ed.). MIT Press and McGraw-Hill. pp. 643–700. ISBN 0-262-53196-8

[1]