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

テンプレート:出典の明記 フォード・ファルカーソンのアルゴリズム（テンプレート:Lang-en-short）とは、フローネットワークにおける最大フローを求めるアルゴリズムである^[1]。テンプレート:仮リンクとテンプレート:仮リンクにちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。

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

アルゴリズム

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

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

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

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

入力フロー容量

c

、始点

s

、終点

t

のグラフ

G

出力

s

から

t

へのフロー

f

の最大値

全ての枝 $(u, v)$ について $f (u, v) \leftarrow 0$ とする。
Gf 内で s から t への経路 p があり、経路上の全ての枝 (u,v)∈p について cf(u,v)>0 であるとき:
1. $c_{f} (p) = \min {c_{f} (u, v) | (u, v) \in p}$ を求める。
2. (u,v)∈p であるような各枝について
  1. $f (u, v) \leftarrow f (u, v) + c_{f} (p)$ （この枝にそってフローを送る）
  2. $f (v, u) \leftarrow f (v, u) - c_{f} (p)$ （フローは後で返される）

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

複雑性

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

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

例

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

経路	容量	フローネットワーク
	初期状態のフローネットワーク
$A, B, C, D$	$\min (c_{f} (A, B), c_{f} (B, C), c_{f} (C, D))$ $= \min (c (A, B) - f (A, B), c (B, C) - f (B, C), c (C, D) - f (C, D))$ $= \min (1000 - 0, 1 - 0, 1000 - 0)$ $= 1$
$A, C, B, D$	$\min (c_{f} (A, C), c_{f} (C, B), c_{f} (B, D))$ $= \min (c (A, C) - f (A, C), c (C, B) - f (C, B), c (B, D) - f (B, D))$ $= \min (1000 - 0, 0 - (- 1), 1000 - 0)$ $= 1$
	1998ステップ後…
	最終的なフローネットワーク