フォード・ファルカーソンのアルゴリズムのソースを表示

{{出典の明記|date=2015年11月}}
'''フォード・ファルカーソンのアルゴリズム'''（{{lang-en-short|Ford-Fulkerson algorithm}}）とは、[[フローネットワーク]]における[[最大フロー問題|最大フロー]]を求める[[アルゴリズム]]である<ref>{{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>。{{仮リンク|レスター・フォード Jr.|en|L. R. Ford, Jr.|de|Lester Randolph Ford junior|fr|Lester Randolph Ford junior|ru|Форд, Лестер}} と {{仮リンク|デルバート・ファルカーソン|en|D. R. Fulkerson|de|Delbert Ray Fulkerson|es|Delbert Ray Fulkerson|fr|Delbert Ray Fulkerson|pt|Delbert Ray Fulkerson|sk|Delbert Ray Fulkerson|vi|Delbert Ray Fulkerson|cs|Delbert Ray Fulkerson}} にちなんで命名されたもので、[[1956年]]に発表された。フォード・ファルカーソンのアルゴリズムの特殊版である[[エドモンズ-カープアルゴリズム]]も「フォード・ファルカーソン」と呼ばれることがある。

この[[アルゴリズム]]の背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; {{Lang|en|augmenting path}}」と呼ぶ。

== アルゴリズム ==
グラフ <math>G(V,E)</math> にて、<math>u</math> から <math>v</math> への容量 <math>c(u,v)</math> でフロー <math>f(u,v)=0</math> とする。ここで、始点 <math>s</math> から終点 <math>t</math> への最大フローを求める。最終的に、次のような状態となる。

* <math>\ f(u,v) \leq c(u,v)</math> : <math>u</math> から <math>v</math> へのフローは容量を超えない。
* <math>\ f(u,v) = - f(v,u)</math> : <math>u</math> と <math>v</math> の間の総フローの性質。<math>u</math> から <math>v</math> へのフローが <math>a</math>、<math>v</math> から <math>u</math> へのフローが <math>b</math> であるとき、<math>f(u,v)=a-b</math> であり、かつ <math>f(v,u)=b-a</math> となる。
* <math>\ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u)</math> : <math>s</math> と <math>t</math> を除く全てのノード <math>u</math> で成り立つ。あるノードに流れ込むフローとそこから出て行くフローは常に等しい。

すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、'''残余ネットワーク''' <math>G_f(V,E_f)</math> を容量が <math>c_f(u,v) = c(u,v) - f(u,v)</math> で、フローのないネットワークと定義する。ただし、<math>u,v</math> のフローによって <math>u,v</math> がクローズ（満杯）となっても <math>v,u</math> は残余ネットワークに残る可能性があるため、<math>E=E_f</math> となるかどうかは定かではない。

'''アルゴリズム''' フォード・ファルカーソン
:'''入力''' フロー容量 <math>\,c</math>、始点 <math>\,s</math>、終点 <math>\,t</math> のグラフ <math>\,G</math>
:'''出力''' <math>\,s</math> から <math>\,t</math> へのフロー <math>\,f</math> の最大値
:# 全ての枝 <math>\,(u,v)</math> について <math>f(u,v) \leftarrow 0</math> とする。
:# <math>\,G_f</math> 内で <math>\,s</math> から <math>\,t</math> への経路 <math>\,p</math> があり、経路上の全ての枝 <math>(u,v) \in p</math> について <math>\,c_f(u,v) > 0</math> であるとき:
:## <math>\,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}</math> を求める。
:## <math>(u,v) \in p</math> であるような各枝について
:### <math>f(u,v) \leftarrow f(u,v) + c_f(p)</math> （この枝にそってフローを送る）
:### <math>f(v,u) \leftarrow f(v,u) - c_f(p)</math> （フローは後で返される）

経路は、<math>G_f(V,E_f)</math> について、例えば[[幅優先探索]]や[[深さ優先探索]]を行うことで得られる。前者の場合を特に[[エドモンズ-カープアルゴリズム]]と呼ぶ。

== 複雑性 ==
フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は [[ランダウの記号|''O'']](''Ef'') であり、''E'' はグラフ内の枝数、''f'' はグラフの最大フローである。これは、増加道が ''O''(''E'') 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。

フォード・ファルカーソンのアルゴリズムの派生として、[[エドモンズ-カープアルゴリズム]]がある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は ''O''(''VE''<sup>2</sup>) となる。

== 例 ==
以下の例は、4ノードのフローネットワークでフォード・ファルカーソンのアルゴリズムを適用する様子を最初の数ステップだけ図示したものである。始点は ''A'' で終点は ''D''。増加道は[[深さ優先探索]]で探し、隣接ノードは辞書順で調べる。この例では、アルゴリズムの最悪ケースを示している。各ステップではフローは1ずつしか増えない。この場合、[[幅優先探索]]で経路を求めると、2ステップで完了する。

{| class="wikitable"
|-
! 経路 !! 容量 !! フローネットワーク
|-
| || 初期状態のフローネットワーク || [[画像:Ford-Fulkerson example 0.svg|300px]]
|-
| <math>A,B,C,D</math>
| <math>\min(c_f(A,B), c_f(B,C), c_f(C,D))</math><br />
<math>= \min(c(A,B)-f(A,B) ,c(B,C)-f(B,C), c(C,D)-f(C,D))</math><br />
<math>=\min(1000-0, 1-0, 1000-0)</math><br>
<math>= 1</math>
| [[画像:Ford-Fulkerson example 1.svg|300px]]
|-
| <math>A,C,B,D</math> 
| <math>\min(c_f(A,C), c_f(C,B), c_f(B,D))</math><br />
<math>= \min(c(A,C)-f(A,C), c(C,B)-f(C,B), c(B,D)-f(B,D))</math><br />
<math>=\min(1000-0, 0-(-1), 1000-0)</math><br>
<math>=1</math>
| [[画像:Ford-Fulkerson example 2.svg|300px]]
|-
| || 1998ステップ後… || 
|-
| || 最終的なフローネットワーク || [[画像:Ford-Fulkerson example final.svg|300px]]
|}

経路 ''A,C,B,D'' を見つけたとき、''C'' から ''B'' へフローが押し戻される点に注意されたい。

== 参考文献 ==
{{reflist}}

== 外部リンク ==
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml Ford-Fulkerson's algorithm] アニメーション解説あり
{{commonscat-inline|Ford-Fulkerson's algorithm}}

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

{{DEFAULTSORT:ふおとふあるかそんのあるこりすむ}}
[[Category:グラフ理論]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:エポニム]]