グラフ理論において強連結成分分解とは, 有向グラフの頂点を以下の条件を満たすようにグループ分けすることです。
$$
任意の2頂点A, Bについて, AとBが同じグループに属する
$$
$$
\iff 有向グラフ上でAからBへの経路, BからAへの経路がともに存在する
$$
自分は競技プログラミングをしていてこの概念を知りました。
このようなグループ分けは, 以下のようなアルゴリズムで達成できることが知られています。
- グラフ上の頂点を1つ選び, そこから到達できる点を深さ優先探索で探索する。
- 探索の帰り際に1から順に頂点に番号をつける。これが終わったらまだ探索されていない点を1つ選び, 同様に深さ優先探索で番号をつけることを, 全ての頂点に番号がつけられるまで繰り返す。一度探索した点は2度以上探索しない。
- グラフの全ての辺を逆向きにし, 2・3でつけた番号の大きい点から順に探索する。一度の探索で訪問した点を同じグループとしてまとめる。
このアルゴリズムが正しいことの証明を調べたのですが見つからなかったので, 自分が考えた証明を書こうと思います(間違っていたら指摘していただけるとありがたいです)。
1. 用語の定義
証明にあたって, 以下の用語を定める。
- 点$X$から$Y$への経路を$\overrightarrow{XY}$と書き, $\overrightarrow{XY}$が存在することを$E(\overrightarrow{XY})$とかく。また$E(\overrightarrow{XX})$が常に成り立つとする。
- 2回の探索のうち1回目の探索を探索1, ｓ2回目の探索を探索2とする。
- 頂点$X$につけられた番号を$p(X)$とする。
- 探索2において, $X$が点$Y$から出発した探索時に訪問されたとき, $g(X)=Y$とする。
2点$A, B$が同じグループにあることは, $g(A)=g(B)$と同値となる。
また定義より,
$$
g(X)=\mathrm{argmax}_{Y: E(\overrightarrow{XY})}p(Y)
$$
である。
$E(\overrightarrow{XX})$であるから, $p(g(X))\ge p(X)$となる。
任意の2点$A, B$に対して
$$
g(A)=g(B)\iff E(\overrightarrow{AB})かつE(\overrightarrow{BA})
$$
であることを示せばよい。
2. $E(\overrightarrow{AB})$かつ$E(\overrightarrow{BA})\implies g(A)=g(B)$の証明
探索2において, 一般性を失わずに$B$より先に$A$を訪問したとしてよい。
$A$訪問時, 探索2の深さ優先探索のスタックに, $\overrightarrow{BA}$の経路上の点がなければ, $A$からの探索において$B$が訪問されるので, $g(A)=g(B)$となる。
$A$訪問時, 探索2の深さ優先探索のスタックに, $\overrightarrow{BA}$の経路上の点が含まれる場合, その中で最も$B$に近い点を$C$とすると, $E(\overrightarrow{BC})$なので, $C$からの探索で$B$が探索される。よって, やはり$g(A)=g(B)$となる。
3. $g(A)=g(B)\implies E(\overrightarrow{AB})$かつ$E(\overrightarrow{BA})$ の証明
$g(A)=g(B)=X$とおく。まず$E(\overrightarrow{AX})$かつ$E(\overrightarrow{XA})$であることを示す。
$X=A$のときは自明なので, $X\ne A$とする。
定義より, $E(\overrightarrow{AX}), p(A)<p(X)$ である。
探索1において, $X$より先に$A$に訪問したとする。
$E(\overrightarrow{AX})$より, $p(X)>p(A)$となるためには, $A$訪問時の深さ優先探索のスタックに$E(\overrightarrow{AX})$の経路上の点が含まれているはずである。その点の中で最も$X$に近い点を$C$とすると,$E({\overrightarrow{AC}})$かつ $E(\overrightarrow{CX})$となり, $\overrightarrow{CX}$上にスタック上の点は存在しないので, $p(X)< p(C)$となる。しかしこのとき$g(A)=C$となり矛盾する。
よって$X$の方が$A$より先に訪問されている。
このとき, $p(A)< p(X)$となるためには, $X$到達後, その下流の探索で$A$に到達する必要があり, $E(\overrightarrow{XA})$であることがわかる。よって$E(\overrightarrow{AX})$かつ$E(\overrightarrow{XA})$が示された。
同様に, $B$についても$E(\overrightarrow{BX})$かつ$E(\overrightarrow{XB})$である。
よって, $A\to X\to B, B\to X\to A$という経路が存在するから, $E(\overrightarrow{AB})$かつ$E(\overrightarrow{BA})$である。