フローネットワークの最小カットの容量を求めるアルゴリズム

グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理, カット, 最小カット

アルゴリズム

最小カットの容量を求めるアルゴリズム:

  1. フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
  2. \(|f^*|\) が最小カットの容量

※ カット \((S,T)\) は \(s \in S\) かつ \(t \in T\) かつ \(T=V~-S\) を満たす
※ カット \((S,T)\) の容量は \(c(S,T) := \sum_{u\in S} \sum_{v \in T} c(u,v)\)
※ 最大フローはFord-Fullkerson法などを用いて求める

計算量

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

  • \(O( |f^*| × |E|)\) (Ford-Fullkerson法を用いる場合)

最大フローの値を求めることになるので、最大フローを求めるのに必要な計算量と同じ時間がかかります。

C++ での実装例

最大フローを求めるアルゴリズムを参考にしてください。

アルゴリズムの正当性

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

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

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

練習問題