フローネットワークの最小カットの容量を求めるアルゴリズム
アルゴリズム
最小カットの容量を求めるアルゴリズム：
- フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
- \(|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)\) を満たす（これは最小カットとなる）