概要
解説がなさそうだったので、書きます。自分の理解の整理も兼ねて。
フローの基礎用語
軽く整理します。用語や記号は、文献によって揺れが大きいですし、私の好みに多少寄せているので、ご了承ください。細かい議論はさぼっているので、初めてフローについて学ぶ人向けというよりは、既習者の復習向けです。
$G = (G, s, t)$ をネットワーク （$G$ は重み付き有向グラフ）とします。辺 $e$ の容量を $\text{cap}_G(e)$ と書きます。
$v\in G$ に対して、$v$ から出ている辺全体の集合を $E_{\text{out}}(v)$, $v$ に向かっている辺全体を $E_{\text{in}}(v)$ と書きます。
フロー
各辺 $e$ に対して実数 $0\leq f(e)\leq \text{cap}_G(e)$ を対応させる規則であって、$s, t$ を除く任意の頂点 $v$ に対して $$\sum_{e\in E_{\text{out}}(v)} f(e) =\sum_{e\in E_{\text{in}}(v)} f(e)$$ が成り立つものを、フローといいます。
頂点集合 $A, B$ に対して、$A-B$ 辺に対する $f$ の和を、$f(A, B)$ と書いたりします。
残余ネットワーク
$f$ を $G$ のフローとします。$G$ の各辺 $e$ に対して
- $e$ の容量を $f(e)$ 減らす
- 容量 $f(e)$ の $e$ の逆辺を張る
として得られるネットワークを、$G$ の $f$ に関する残余ネットワークといい、$G_f$ と書きます。
カット
頂点集合 $V(G)$ の分割 $(S, T)$ であって、$s\in S$ かつ $t\in T$ となるものを、ネットワーク $G$ のカットといいます。
$(S,T)$ をカットとします。トータルで $S$ から $T$ に流れ出る量 $f(S, T) – f(T, S)$ の値は、カット $(S, T)$ のとり方によらないことが証明できます。この値をフロー $f$ の流量 といい、$|f|$ と書きます。
$S-T$ 辺 $e$ に対する $\text{cap}_{G}(e)$ の和を、カット $(S,T)$ のカット容量 といい、$\text{cap}_G(S,T)$ と書きます。
$|f| = f(S, T) – f(T, S) \leq f(S, T) \leq \text{cap}_G(S, T)$ ですから、任意のフローとカットに対して、流量はカット容量以下になります。
残余ネットワークとカット容量
残余ネットワークのカット容量について、次が成り立ちます。
【命題】ネットワーク $G$ の、フロー $f$ に関する残余ネットワークを $G_f$ とする。このとき、任意のカット $(S, T)$ に対して、$\text{cap}_{G_f}(S, T) = \text{cap}_{G}(S, T) – |f|$ が成り立つ。特に、$(S, T)$ が $G$ の最小カットであることと、$(S, T)$ が $G_f$ の最小カットであることは同値である。
わりと簡単です。$\text{cap}_{G_f}(S, T)$ は、$G_f$ における $S-T$ 辺の容量の和です。この和のうち、
- $G_f$ の $S-T$ 辺のうち、$G$ の辺に対応するものの寄与は、$\text{cap}_G(S,T) – f(S, T)$ に等しい。
- $G_f$ の $S-T$ 辺のうち、$G$ の辺の逆辺に対応するものの寄与は、$f(T, S)$ に等しい。
ことが容易に確かめられます。したがって、$\text{cap}_{G_f}(S, T) = \text{cap}_G(S,T) – f(S,T)+f(T,S)$ であることが分かり、$|f| = f(S, T) – f(T, S)$ と合わせて主張を得ます。
系として、超有名な、最大流・最小カット定理が得られます。
【系】最大流と最小カットは等しい。
ここでは最大流の存在は認めて、証明を確認します。（最大流の存在は、例えばコンパクト集合上の連続関数は最大値を持つという一般論から分かります。）
最大流 $f$ をひとつとり、残余ネットワーク $G_f$ を考える。$G_f$ において、容量正の辺だけを用いた $s-t$ パスがあると、そのパスを加えることで $f$ よりも流量の大きなフローが作れてしまい矛盾する。よって、$G_f$ において、容量正の辺だけを用いた $s-t$ パスは存在しない。
すると、$s$ から容量正の辺だけを用いて到達できる頂点全体を $S$ として分割 $(S,T)$ を作れる。$S-T$ 辺の容量は全て $0$ なので、そのカット容量は $0$ である。特に $G_f$ の最小カット容量は $0$ である。命題よりこれは $G$ の最小カット容量から $|f|$ を引いた値に等しいので示された。
残余ネットワークと最小カット
ネットワーク $G$ の、最大流 $f$ をひとつとり、残余ネットワークを $G_f$ とします。
また、以下では、$G_f$ のうち容量が正の辺だけを残した部分グラフを考え、それを改めて $G_f$ と書くことにします。
カット $(S, T)$ が $G$ の最小カットであることと、$G_f$ の最小カットであることは同値なのでした。このことから、$G$ の最小カットを、より分かりやすい形でとらえることができます。
【系】$(S,T)$ が $G$ の最小カットであることは、残余ネットワーク $G_f$ において $S-T$ 辺が存在しないことと同値である。
問題の解法
頂点 $c, d$ に対して、
- 頂点 $c, d$ を分離するような最小カット $(S,T)$ が存在するか
- 頂点 $c, d$ を分離しないような最小カット $(S,T)$ が存在するか
を判定する問題です。適当な最大流をひとつ求めて残余ネットワークをとり、容量が正の辺のみを残すことで、次に帰着できます。
【問題】$G$ を $s-t$ パスが存在しないような有向グラフとする。$S-T$ 辺が存在しないようなカット $(S, T)$ であって $s\in S, t\in T$ を満たすもののうちで、$c, d$ を分離するようなもの、しないようなものの存在を判定せよ。
まず、頂点を $3$ タイプに分類しておきます。
- タイプ A：$s$ から到達可能な頂点
- タイプ B：$t$ へ到達可能な頂点
- タイプ C：その他
ある頂点がタイプ A, B の両方であることはない（$s-t$ パスの非存在より）ことに注意してください。答は以下の通りです。
- タイプ A の頂点同士は、分離不可能
- タイプ B の頂点同士は、分離不可能
- タイプ A の頂点と、タイプ B の頂点は、常に分離される
- タイプ A の頂点とタイプ C の頂点は、分離することも分離しないことも可能
- タイプ B の頂点とタイプ C の頂点は、分離することも分離しないことも可能
- タイプ C の頂点同士で、同じ強連結成分に含まれないものは、分離することも分離しないことも可能
- タイプ C の頂点同士で、同じ強連結成分に含まれるならば分離不可能
このことを確認しましょう。
$S-T$ 辺を含まないカット $(S,T)$ で $s\in S$ かつ $t\in T$ を満たすものについて、タイプ A の頂点は常に $S$, タイプ B の頂点は常に $T$ に含まれることが分かります。このことから、1. 2. 3. の場合について示すことができます。
また、同じ強連結成分に含まれる $2$ 点は、$S$, $T$ に分けてしまうと $S-T$ 辺ができてしまうため、分離不可能です（7. の場合）。
残りは 4. 5. 6. の場合です。これは、タイプ B → タイプ C → タイプ A の順に強連結成分が並ぶように強連結成分をトポロジカルソートして、適当な境界線でソート順前半・後半の強連結成分の和集合を $S$, $T$ とすることにより、分離する場合・しない場合ともにカットを構成可能です。
以上により、本問題を解くことができました。
- 最大流を求め、残余ネットワークを得る。容量 $0$ の辺は捨てる。
- 残余ネットワークにおいて、$s$ から、あるいは $t$ への到達可能性を判定する。
- 強連結成分分解を求める。
- クエリごとに、上で述べた方法で判定し、結果を出力する
という手順で正答が得られます。
コメント
最大流・最小カット定理の証明については、ソラですぐに言える程度には理解しているつもりでしたが、残余グラフが最小カットを保つという事実は明示的に認識したことはなかったです。自身の学びも兼ねて、細かい議論を記事にしてみました。
