書記が数学やるだけ#623 フォード-ファルカーソンのアルゴリズム

最大フローを求めるアルゴリズムのうち，フォード-ファルカーソンのアルゴリズムについて今回は見ていく。

問題

実際に最大フローを求めてみる。

説明

ポイントとなるのは，増加道の有無である。

解答

最大流であることと増加道を含まないことの同値を示しておく。

初期値として0フローを与え，残余ネットワークを求める。適当に経路を選び，ボトルネックとなっているところを最大流とする。

改めて残余ネットワークを作ると，もう通ることのできない経路が出てくるので，それを避けた経路を作る。

最終的に，通ることのできる経路がなくなるので，これが最大フローを与える経路であると言える。

本記事のもくじはこちら：