最大フロー問題のソースを表示

[[画像:Max flow.svg|thumb|right|最大フローのあるフローネットワークの例。始点 <math>s</math> と終点 <math>t</math> があり、各枝の数値はフローと容量を示す。]]
'''最大フロー問題'''（さいだいフローもんだい、{{lang-en-short|Maximum flow problem}}）または'''最大流問題'''とは、単一の始点から単一の終点への[[フローネットワーク]]で最大となるフローを求める問題である<ref name="ia">{{Cite book |和書 |author1=T. コルメン |author2=R. リベスト |author3=C. シュタイン |author4=C. ライザーソン |origdate=2009-7-31 |date=2013-12-17 |edition=第3版 |title=アルゴリズムイントロダクション |language=日本語 |publisher=近代科学社 |isbn=476490408X }}</ref>。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である[[最小費用流問題]]の特殊ケースと見ることもできる。

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

'''2部グラフの最大マッチング問題'''（{{lang-en-short|Maximum bipartite matching}}）とは、[[2部グラフ]]の最大[[マッチング (グラフ理論)|マッチング]]を求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける<ref name="ia"/>。

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

{| class="wikitable"
! 発表年
! 名称
! 計算量
! 説明
|-
|
| [[線形計画法]]
| 
| 正規フローの定義から制約条件が与えられる。<math>\sum_{v \in V} f(s,v)</math> を最大化。
|-
| nowrap | 1956年
| [[フォード・ファルカーソンのアルゴリズム]]
| <math>O(E \cdot \text{maxflow})</math>
| 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。
|-
| 1970年
| [[エドモンズ・カープのアルゴリズム]]
| <math>O(VE^2)</math>
| フォード・ファルカーソンの特殊ケースであり、[[幅優先探索]]で増加道を探す。
|-
| 1970年
| [[ディニッツ法]]
| <math>O(V^2 E)</math>
| ステップ毎に[[残余グラフ]]について[[幅優先探索]]で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは <math>O(VE)</math> で求められ、ステップの反復は最大 <math>n-1</math> 回である。
|-
| 1978年
| MPM法<ref>{{cite journal |last1=Malhotra |first1=V.M. |last2=Kumar |first2=M.Pramodh |last3=Maheshwari |first3=S.N. |title=An O( |V |3) algorithm for finding maximum flows in networks |journal=Information Processing Letters |volume=7 |issue=6 |year=1978 |pages=277–278 |issn=00200190 |doi=10.1016/0020-0190(78)90016-9 }}</ref>
| <math>O(V^3)</math>
| Malhotra, Pramodh-Kumar, Maheshwari が発表。
|-
| 1981年
| 動的木を使ったディニッツ法<ref>{{Cite journal |author=Daniel Dominic Kaplan Sleator |title=An o(nm log n) algorithm for maximum network flow }}</ref>
| <math>O(VE \log V)</math>
| 層別グラフのブロッキングフロー計算を[[動的木]]を使うことで <math>O(E \log V)</math> で行う。
|-
| 1986年
| 汎用[[プッシュ再ラベル法]]<ref name="new_approach">{{cite journal |last1=Goldberg |first1=A V |last2=Tarjan |first2=R E |title=A new approach to the maximum flow problem |year=1986 |pages=136–146 |doi=10.1145/12130.12144 }}</ref>
| <math>O(V^2E)</math>
| プリフロー（頂点群で超過する可能性のあるフロー関数）を使うアルゴリズム。正の超過のある頂点（グラフ内のアクティブな頂点）がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。
|-
| 1986年
| FIFO式頂点選択規則付きプッシュ再ラベル法<ref name="new_approach"/>
| <math>O(V^3)</math>
| 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。
|-
| 1986年
| 動的木を使ったプッシュ再ラベル法<ref name="new_approach"/>
| <math>O(VE\log(V^2/E))</math>
| height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。
|-
| 1994年
| KRT (King, Rao, Tarjan) 法<ref>{{cite journal |last1=King |first1=V. |last2=Rao |first2=S. |last3=Tarjan |first3=R. |title=A Faster Deterministic Maximum Flow Algorithm |journal=Journal of Algorithms |volume=17 |issue=3 |year=1994 |pages=447–474 |issn=01966774 |doi=10.1006/jagm.1994.1044 }}</ref>
| <math>O(EV \log_{E/V \log V}V)</math>
|
|-
| 1998年
| バイナリブロッキングフロー法<ref>{{cite journal |last1=Goldberg |first1=Andrew V. |last2=Rao |first2=Satish |title=Beyond the flow decomposition barrier |journal=Journal of the ACM |volume=45 |issue=5 |year=1998 |pages=783–797 |issn=00045411 |doi=10.1145/290179.290181 }}</ref>
| <math>O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})</math>
| 計算量の <math>U</math> はネットワークの最大容量。
|-
| 2013年
| Jim Orlin法 + KRT (King, Rao, Tarjan) 法<ref>{{cite journal |last1=Orlin |first1=James B. |title=Max flows in O(nm) time, or better |year=2013 |pages=765 |doi=10.1145/2488608.2488705 }}</ref>
| <math>O(VE)</math>
| Jim Orlin法自体は<math>O(VE + E^{31/16} \log^2 V)</math>だが、KRT法を組み合わせることで<math>O(VE)</math>になる。
|}

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*{{cite journal |author=Daniel D. Sleator and [[ロバート・タージャン|Robert E. Tarjan]] |title=A data structure for dynamic trees |journal=Journal of Computer and System Sciences |volume=26 |number=3 |year=1983 |issn=0022-0000 |pages=362&ndash;391 |doi=10.1016/0022-0000(83)90006-5 |url=https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf }}
*{{cite journal |author=Daniel D. Sleator and [[ロバート・タージャン|Robert E. Tarjan]] |title=Self-adjusting binary search trees |journal=Journal of the ACM |volume=32 |number=3 |year=1985 |issn=0004-5411 |pages=652&ndash;686 |doi=10.1145/3828.3835 |publisher=ACM Press |location=New York, NY, USA |url=https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf }}
*{{cite journal |author=Andrew V. Goldberg and [[ロバート・タージャン|Robert E. Tarjan]] |title=A new approach to the maximum-flow problem |journal=Journal of the ACM |volume=35 |number=4 |year=1988 |issn=0004-5411 |pages=921&ndash;940 |doi=10.1145/48014.61051 |publisher=ACM Press |location=New York, NY, USA |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.1599 |ref={{SfnRef|Goldberg and Tarjan|1988}} }}
*{{cite journal |author=Joseph Cheriyan and Kurt Mehlhorn |title=An analysis of the highest-level selection rule in the preflow-push max-flow algorithm |journal=Information Processing Letters |volume=69 |number=5 |year=1999 |pages=239&ndash;242 |doi=10.1016/S0020-0190(99)00019-8 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8563 }}

{{最適化アルゴリズム}}
{{アルゴリズム}}

{{DEFAULTSORT:さいたいふろおもんたい}}
[[Category:グラフ理論]]
[[Category:オペレーションズリサーチ]]
[[Category:数学に関する記事]]