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

フォード・ファルカーソンアルゴリズム：最大フロー問題へのアプローチ

フォード・ファルカーソンアルゴリズムは、フローネットワークにおいて始点から終点への最大フローを計算するためのアルゴリズムです。レスター・フォードJr.とデルバート・ファルカーソンによって1956年に発表され、そのシンプルさと有用性から、グラフ理論やネットワーク最適化の分野で広く活用されています。本アルゴリズムは、増加道（augmenting path）と呼ばれる、始点から終点への容量に余裕のある経路を繰り返し探索することで、最大フローを求めます。

アルゴリズムの基礎

アルゴリズムは、ノード（頂点）の集合Vと枝（辺）の集合Eからなる有向グラフG(V,E)を対象とします。各枝(u,v)には、容量c(u,v)が設定されており、これはその枝を通過できるフローの上限を表します。始点sと終点tが与えられ、sからtへの最大フローを求めることがアルゴリズムの目的です。

アルゴリズムは、初期フローを0として開始します。そして、以下のステップを繰り返し実行します。

1. 増加道の探索: 現在のフローfに基づいて、残余ネットワークGfを構築します。残余ネットワークとは、各枝(u,v)の残余容量cf(u,v) = c(u,v) - f(u,v)によって定義されるグラフです。残余容量は、その枝にさらにどれだけのフローを追加できるかを示します。sからtへの残余容量が正の経路（増加道）が存在すれば、それを探します。増加道の探索には、幅優先探索や深さ優先探索などのグラフ探索アルゴリズムが利用できます。

2. フローの増加: 増加道pが見つかった場合、その経路上で最小の残余容量cf(p) = min{cf(u,v) | (u,v)∈p}を計算します。この値だけ、増加道の各枝のフローを増加させます。具体的には、増加道の各枝(u,v)について、f(u,v) ← f(u,v) + cf(p) と更新します。逆向きの枝(v,u)が存在する場合、f(v,u) ← f(v,u) - cf(p) と更新します。

3. 繰り返し: ステップ1とステップ2を、sからtへの増加道が存在しなくなるまで繰り返します。増加道が存在しなくなった時点で、現在のフローが最大フローとなります。

残余ネットワークとフローの性質

残余ネットワークは、現在のフロー状況を考慮した上で、さらにフローを増やすことができる経路を効率的に探索するために用いられます。各ノードでのフロー保存則（流入量＝流出量）は常に満たされ、アルゴリズムの各ステップで正当なフローが維持されます。

具体的には、以下の条件が常に成り立ちます。

f(u,v) ≤ c(u,v): 各枝のフローは容量を超えない
f(u,v) = -f(v,u): 枝(u,v)と(v,u)のフローは互いに逆向き
* Σv f(u,v) = 0 (u≠s,t): sとt以外のノードでは、流入量と流出量が等しい

計算量とエドモンズ・カープアルゴリズム

フォード・ファルカーソンアルゴリズムの計算量は、最悪の場合O(Ef)となります。ここで、Eは枝の数、fは最大フローの値です。容量が整数値の場合、このアルゴリズムは必ず終了しますが、最大フローの値が非常に大きい場合、計算時間は非常に長くなる可能性があります。

エドモンズ・カープアルゴリズムは、フォード・ファルカーソンアルゴリズムの改良版であり、幅優先探索を用いることで、必ず多項式時間で終了することが保証されています。その計算量はO(VE²)となります。ここで、Vはノードの数です。

例題

具体的な例題を通して、アルゴリズムの動作を確認することができます。例えば、4つのノードからなる単純なネットワークにおいて、増加道を深さ優先探索によって求める過程をステップごとに追跡することで、アルゴリズムの挙動を理解することができます。この際、最悪ケースではフローが1ずつしか増加しない状況も発生しうることに注意が必要です。

まとめ

フォード・ファルカーソンアルゴリズムは、最大フロー問題を解くための基本的なアルゴリズムであり、そのシンプルさと理解しやすさから、グラフ理論の入門としても適しています。しかし、最悪ケースの計算時間が長くなる可能性があるため、より効率的なエドモンズ・カープアルゴリズムなどの改良版も広く利用されています。様々なネットワーク最適化問題への応用が期待できるアルゴリズムです。

もう一度検索