どのようなアルゴリズム?

フォード・ファルカーソン法は最大フロー問題を解く最も代表的なアルゴリズムです. このアルゴリズムを理解するには以下の内容について知る必要があります.

アルゴリズムの中身

端的に言えば, フォード・ファルカーソン法とは

<aside> 📌

残余ネットワーク上の経路に沿ってフローを流し, 残余ネットワークを更新するという操作を可能な限り繰り返す

</aside>

というアルゴリズムです. 実行例としては以下のような感じになります.

残余ネットワーク(右図)に沿ってフローを追加し, この追加に応じて残余ネットワークを更新していく.

ネットワーク $N$ 上のフロー $f$ に対する残余ネットワーク $N_f$ を考えます. ネットワーク $N$ に含まれる有向辺 $(u,v)$ に対し,

残余ネットワーク $N_f$ が辺 $(u,v)$ を持つということは, $u$ から $v$ への流量を増やせることを意味します.
残余ネットワーク $N_f$ が辺 $(v,u)$ を持つということは, 現在の $u$ から $v$ への流量を減らせることを意味します. このことは相対的に見ると, $v$ から $u$ へ流すフローを流していると見なすこともできます.

従って, 残余ネットワーク内に $st$-経路が存在するならば, その経路に沿ってフローをより多く流せるので流量を増やすことができます. このことから, 残余ネットワーク内の $st$-経路のことをそのフローに対する増加路と呼びます.

増加路 $P$ に含まれる辺を $e_1,e_2,\dots,e_m$ とし, それぞれの容量を $c(e_i)$ とします. これらの最小値 $\min\{ c(e_i)\}$ を $P$ のボトルネックといいます. 辺 $e_i$ に沿って流せるフローの流量は高々$c(e_i)$ なので, 増加路に沿って流せるフローの流量はその増加路のボトルネック以下になります.

ダウンロード (3).png

なお, 増加路の辺 $(v,u)$ が元のネットワーク$N$ の辺$(u,v)$ の逆向きになっている場合は, $N$ の辺$(u,v)$ に沿って流すフローの流量を減らします.