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

フォード・ファルカーソンのアルゴリズム（）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。
このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; 」と呼ぶ。
アルゴリズム.
グラフ formula_1 にて、formula_2 から formula_3 への容量 formula_4 でフロー formula_5 とする。ここで、始点 formula_6 から終点 formula_7 への最大フローを求める。最終的に、次のような状態となる。
すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、残余ネットワーク formula_26 を容量が formula_27 で、フローのないネットワークと定義する。ただし、formula_28 のフローによって formula_28 がクローズ（満杯）となっても formula_30 は残余ネットワークに残る可能性があるため、formula_31 となるかどうかは定かではない。
アルゴリズム フォード・ファルカーソン
経路は、formula_26 について、例えば幅優先探索や深さ優先探索を行うことで得られる。前者の場合を特にエドモンズ-カープアルゴリズムと呼ぶ。
複雑性.
フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は "O"("Ef") であり、"E" はグラフ内の枝数、"f" はグラフの最大フローである。これは、増加道が "O"("E") 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。
フォード・ファルカーソンのアルゴリズムの派生として、エドモンズ-カープアルゴリズムがある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は "O"("VE"2) となる。
例.
以下の例は、4ノードのフローネットワークでフォード・ファルカーソンのアルゴリズムを適用する様子を最初の数ステップだけ図示したものである。始点は "A" で終点は "D"。増加道は深さ優先探索で探し、隣接ノードは辞書順で調べる。この例では、アルゴリズムの最悪ケースを示している。各ステップではフローは1ずつしか増えない。この場合、幅優先探索で経路を求めると、2ステップで完了する。
経路 "A,C,B,D" を見つけたとき、"C" から "B" へフローが押し戻される点に注意されたい。