Ford-Fullkerson法による最大フローの値を求めるアルゴリズム

2020年3月19日グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理

アルゴリズム

最大フローを求めるアルゴリズム(Ford-Fullkerson法):

  1. フロー \(f\) を 0 としてはじめる
  2. ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \(G_f\) に存在する間は以下を繰り返す
    • フロー \(f\) を \(p\) に沿って増やす
  3. フロー \(f\) の流量 \(|f|\) を返す

※ 残余ネットワークは、「後どれだけフローを流せるか」を表す残余容量を重みとしたグラフのこと。
※ 増加可能経路は、正の容量を持つ辺のみからなる、ソースからシンクへのパスのこと。
※ フローの基本となる用語の説明はこちら

2. では深さ優先探索や幅優先探索などを用いて、以下のような増加可能経路を探します。

フロー \(f\)
残余ネットワーク \(G_f\)(水色:ある増加可能経路 \(p\))

計算量

最大フローを \(f^*\) 、容量を整数とした時、計算量は以下のようになります。

  • \(O( |f^*| × |E|)\)

フローを増加可能経路に沿って増やすごとに、フローの値は 1 以上増えていくので、繰り返しの回数は高々 \(|f*|\) 回です。

フローを増加可能経路に沿って増やすためには、深さ優先探索か幅優先探索を用いれば良いので、\(O(|E|)\) で計算を行うことができます。

実際は、一回ごとに増えるフローの値が 1 しかないことは少ないので、この見積もりよりも高速に動くことが多いです。

C++ での実装例

残余ネットワークを上手く更新していくために、辺を表す Edge 構造体と、グラフ(残余ネットワーク)を表す Graph 構造体を用いています。

アルゴリズムの正当性

さきほどのアルゴリズムが正しく動作するのは、以下の定理によって分かります。

最大フロー・最小カット定理

以下は全て同値となる。
 1. \(f\) は \(G\) における最大フロー
 2. 残余ネットワーク \(G_f\) は増加可能経路を含まない
 3.\(G\) のカット \((S,T)\) が存在して、 \(|f| = c(S,T)\) を満たす(これは最小カットとなる)

この定理によれば、残余ネットワーク \(G_f\) は増加可能経路を含まないことと、\(f\) が \(G\) における最大フローとなることは必要十分です。

つまり、増加可能経路が無くなった時点で、その時のフローが最大であることが分かります。

練習問題