2015/09/25

強連結成分分解の意味とアルゴリズム

分野: グラフ理論  レベル: 大学数学

深さ優先探索を2回すれば強連結成分分解できる。

強連結成分分解とは

有向グラフにおいて「お互いに行き来できる $\iff$ 同じグループ」を満たすように頂点をグループ分けすることを強連結成分分解と言います。

強連結成分分解の例

例えば図において頂点 $a$ から $c$,$c$ から $a$ はそれぞれ矢印をたどっていけるので同じグループ(強連結成分)に属します。一方,頂点 $d$ から $c$ へのパスは存在しないので,$c$ と $d$ は異なる強連結成分に属します。

図の場合,強連結成分分解は $\{\{a,b,c\},\{d,e\},\{f\},\{g\}\}$ となります。

強連結成分分解のアルゴリズム

前提知識として深さ優先探索が必要です。→深さ優先探索と幅優先探索

  1. 適当な頂点から深さ優先探索を行う,その際各頂点 $v$ に対して頂点 $v$ から進めなくなった順番 $t(v)$ を格納する。
  2. グラフの矢印を全て逆向きにしたものに対して深さ優先探索を行う。その際 $t(v)$ が大きい頂点からスタートする。行き止まったところまでを一つの連結成分とする。

強連結成分分解のアルゴリズム
  1. まず適当な頂点 $a$ から深さ優先探索をする。 $a→b→c→d→e→f$ まで行ってぶつかる。 $f$ から進めないので $t(f)=1$ とする。次に $e$ に戻ると $g$ に進める。 $g$ から進めないので $t(g)=2$ 。 $e$ に戻ると $e$ から進めないので $t(e)=3$ 。以下同様。
  2. 次に枝を逆向きにした有向グラフで深さ優先探索を行う。 $t(v)$ が一番大きい頂点 $a$ からスタート。 $a→c→b$ まで進んで行き止まるので $\{a,b,c\}$ が一つの連結成分。残った頂点の中で $t(v)$ が一番大きい頂点 $d$ からもう一度深さ優先探索。 $d→e$ と進んで行き止まるので $\{d,e\}$ が一つの連結成分。以下同様。

ちなみに深さ優先探索は線形時間なので,強連結成分分解のアルゴリズムの計算量も線形,つまり $O(|V|+|E|)$ です。

アルゴリズムの正しさの証明

アルゴリズムの正しさ

(証明の概略)
出力した一つの頂点集合 $V’$が確かに強連結成分であることを示す。2の深さ優先探索で得られる(頂点集合が $V’$である)木を $T$ とし,その根を $v$ とする。

成分内の二つの頂点が互いに行き来できること

成分内の任意の頂点 $u$ に対して,
(i)枝を逆向きにしたグラフで $v$ から $u$ へのパスがあるのでもとのグラフで $u$ から $v$ へのパスがある。
(ii)$ t(v) > t(u)$ であることと(i)よりもとのグラフで $v$ から $u$ へのパスがある(→注)。

他の頂点からこの成分にはたどりつけないこと

$T$ から他の頂点には枝が伸びていないので,もとのグラフで他の頂点から $V’$の頂点へはたどりづけない。

注:理由をちゃんと書くと少し長くなるので省略しました。難しくないので考えてみてください!

強連結成分分解という名前はかなり強そうです。
分野: グラフ理論  レベル: 大学数学