Warning: Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297
Warning: Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660
Warning: session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127
Warning: session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133
Warning: session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 http:///mymemo.xyz/wiki/api.php?action=feedcontributions&feedformat=atom&user=112.136.23.31miniwiki - 利用者の投稿記録 [ja]2024-06-20T10:13:00Z利用者の投稿記録MediaWiki 1.31.0最大フロー問題2016-04-18T13:58:54Z<p>112.136.23.31: 不正確/不適切な記述を改善.</p>
<hr />
<div>[[画像:Max flow.svg|thumb|right|最大フローのあるフローネットワークの例。始点 <math>s</math> と終点 <math>t</math> があり、各枝の数値はフローと容量を示す。]]<br />
'''最大フロー問題'''または'''最大流問題'''（{{lang-en-short|Maximum flow problem}}）とは、単一の始点から単一の終点への[[フローネットワーク]]で最大となるフローを求める問題である<ref name="ia">{{Cite book|和書<br />
|author1 = T. コルメン<br />
|author2 = R. リベスト<br />
|author3 = C. シュタイン<br />
|author4 = C. ライザーソン<br />
|origdate = 2009-7-31<br />
|date = 2013-12-17<br />
|edition = 第3版<br />
|title = アルゴリズムイントロダクション<br />
|language = 日本語<br />
|publisher = 近代科学社<br />
|isbn = 476490408X<br />
}}</ref>。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である[[最小費用流問題]]の特殊ケースと見ることもできる。<br />
<br />
'''最小カット問題'''（{{lang-en-short|Minimum cut problem}}）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小[[カット (グラフ理論)|カット]]と等しい。これを[[最大フロー最小カット定理]]と呼ぶ。<br />
<br />
'''2部グラフの最大マッチング問題'''（{{lang-en-short|Maximum bipartite matching}}）とは、[[2部グラフ]]の最大[[マッチング (グラフ理論)|マッチング]]を求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける<ref name="ia"/>。<br />
<br />
== 解法 ==<br />
有向[[グラフ理論|グラフ]] <math>G(V,E)</math> において、各枝 <math>u,v</math> の容量を <math>c(u,v)</math> としたとき、始点 <math>s</math> から終点 <math>t</math> への最大フロー <math>f</math> を求める。この問題の解法アルゴリズムは多数存在する。<br />
<br />
{| class="wikitable"<br />
! 発表年<br />
! 名称<br />
! 計算量<br />
! 説明<br />
|-<br />
|<br />
| [[線形計画法]]<br />
| <br />
| 正規フローの定義から制約条件が与えられる。<math>\sum_{v \in V} f(s,v)</math> を最大化。<br />
|-<br />
| nowrap | 1956年<br />
| [[フォード・ファルカーソンのアルゴリズム]]<br />
| <math>O(E \cdot \text{maxflow})</math><br />
| 残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。<br />
|-<br />
| 1970年<br />
| [[エドモンズ・カープのアルゴリズム]]<br />
| <math>O(VE^2)</math><br />
| フォード・ファルカーソンの特殊ケースであり、[[幅優先探索]]で増加道を探す。<br />
|-<br />
| 1970年<br />
| Dinic法<br />
| <math>O(V^2 E)</math><br />
| ステップ毎に[[残余グラフ]]について[[幅優先探索]]で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは <math>O(VE)</math> で求められ、ステップの反復は最大 <math>n-1</math> 回である。<br />
|-<br />
| 1978年<br />
| MPM法<ref>{{Cite doi|10.1016/0020-0190(78)90016-9}}</ref><br />
| <math>O(V^3)</math><br />
| Malhotra, Pramodh-Kumar, Maheshwari が発表。<br />
|-<br />
| 1981年<br />
| 動的木を使ったDinic法<ref>{{Cite journal<br />
|author = Daniel Dominic Kaplan Sleator <br />
|title = An o(nm log n) algorithm for maximum network flow<br />
}}</ref><br />
| <math>O(VE \log V)</math><br />
| 層別グラフのブロッキングフロー計算を[[動的木]]を使うことで <math>O(E \log V)</math> で行う。<br />
|-<br />
| 1986年<br />
| 汎用プッシュ再ラベル法<ref name="new_approach">{{cite doi|10.1145/12130.12144}}</ref><br />
| <math>O(V^2E)</math><br />
| プリフロー（頂点群で超過する可能性のあるフロー関数）を使うアルゴリズム。正の超過のある頂点（グラフ内のアクティブな頂点）がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。<br />
|-<br />
| 1986年<br />
| FIFO式頂点選択規則付きプッシュ再ラベル法<ref name="new_approach"/><br />
| <math>O(V^3)</math><br />
| 最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。<br />
|-<br />
| 1986年<br />
| 動的木を使ったプッシュ再ラベル法<ref name="new_approach"/><br />
| <math>O(VE\log(V^2/E))</math><br />
| height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。<br />
|-<br />
| 1994年<br />
| KRT (King, Rao, Tarjan) 法<ref>{{cite doi|10.1006/jagm.1994.1044}}</ref><br />
| <math>O(EV \log_{E/V \log V}V)</math><br />
|<br />
|-<br />
| 1998年<br />
| バイナリブロッキングフロー法<ref>{{cite doi|10.1145/290179.290181}}</ref><br />
| <math>O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})</math><br />
| 計算量のUはネットワークの最大容量。<br />
|-<br />
| 2013年<br />
| Jim Orlin法 + KRT (King, Rao, Tarjan) 法<ref>{{cite doi|10.1145/2488608.2488705}}</ref><br />
| <math>O(VE)</math><br />
| Jim Orlin法自体は<math>O(VE + E^{31/16} \log^2 V)</math>だが、KRT法を組み合わせることで<math>O(VE)</math>になる。<br />
|}<br />
<br />
これら以外にも解法アルゴリズムは多数存在し、参考文献（特に Goldberg and Tarjan 1988）を参照されたい。<br />
<br />
== 脚注・出典 ==<br />
{{Reflist}}<br />
<br />
== 参考文献 ==<br />
* {{cite journal<br />
| author = Daniel D. Sleator and [[ロバート・タージャン|Robert E. Tarjan]]<br />
| title = A data structure for dynamic trees<br />
| journal = Journal of Computer and System Sciences<br />
| volume = 26<br />
| number = 3<br />
| year = 1983<br />
| issn = 0022-0000<br />
| pages = 362&ndash;391<br />
| doi = 10.1016/0022-0000(83)90006-5<br />
| url = http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf<br />
}}<br />
* {{cite journal<br />
| author = Daniel D. Sleator and [[ロバート・タージャン|Robert E. Tarjan]]<br />
| title = Self-adjusting binary search trees<br />
| journal = Journal of the ACM<br />
| volume = 32<br />
| number = 3<br />
| year = 1985<br />
| issn = 0004-5411<br />
| pages = 652&ndash;686<br />
| doi = 10.1145/3828.3835<br />
| publisher = ACM Press<br />
| location = New York, NY, USA<br />
| url = http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf<br />
}}<br />
* {{cite journal<br />
| author = Andrew V. Goldberg and [[ロバート・タージャン|Robert E. Tarjan]]<br />
| title = A new approach to the maximum-flow problem<br />
| journal = Journal of the ACM<br />
| volume = 35<br />
| number = 4<br />
| year = 1988<br />
| issn = 0004-5411<br />
| pages = 921&ndash;940<br />
| doi = 10.1145/48014.61051<br />
| publisher = ACM Press<br />
| location = New York, NY, USA<br />
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.1599<br />
}}<br />
* {{cite journal<br />
| author = Joseph Cheriyan and Kurt Mehlhorn<br />
| title = An analysis of the highest-level selection rule in the preflow-push max-flow algorithm<br />
| journal = Information Processing Letters<br />
| volume = 69<br />
| number = 5<br />
| year = 1999<br />
| pages = 239&ndash;242<br />
| doi = 10.1016/S0020-0190(99)00019-8<br />
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8563<br />
}}<br />
<br />
{{アルゴリズム}}<br />
<br />
{{DEFAULTSORT:さいたいふろもんたい}}<br />
[[Category:グラフ理論]]<br />
[[Category:オペレーションズリサーチ]]<br />
[[Category:数学に関する記事]]</div>112.136.23.31 Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46