スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

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

有向グラフの強連結成分を O(|V|+|E|) 時間で求めるのに、Kosaraju のアルゴリズムはよく知られている。
これは、もとのグラフと逆グラフに対してそれぞれ DFS を行うもので、強連結成分分解のアルゴリズムとしては最もポピュラーである。

Kosaraju のアルゴリズムがなぜ正しく動くのかが直観的にわからなかったので、気になって調べてみた。
この記事では雰囲気を説明するだけにとどめる。
完全な証明は、たとえば
[1] エイホ,ホップクロフト,ウルマン 『データ構造とアルゴリズム』
[2] コルメン,ライザーソン,リベスト,シュタイン 『アルゴリズムイントロダクション 第 2 巻』
にある。

Tags : グラフ理論, アルゴリズム

記号

G = (V, E) : 有向グラフ
G' = (V, E') : G の辺の方向を反転してできる逆グラフ
C(u) : u ∈ V を含む G の強連結成分

説明

Kosaraju のアルゴリズムは既知とする。
アルゴリズムがなぜ正しく動くかを説明する。

G における DFS では、G の頂点に帰りがけ順で番号をつけている。
これが、実は G の強連結成分を縮約してできる DAG のトポロジカル順序 ( の逆 ) に対応している。

G' における DFS では、さっきつけた番号の大きい頂点から調べていく。

G' における 1 回目の DFS を考える。
頂点 x から DFS を開始したとする。
この結果得られる頂点集合を D(x) とする。

(i) D(x) ⊃ C(x) は明らか。
なぜなら、G' には x から C(x) の任意の頂点へのパスがあるから。
( G と G' の強連結成分分解が一致するということを暗に使っている。 )

(ii) D(x) ⊂ C(x) がいえる。
ここで、帰りがけ順の番号付けが利いている。
u ∈ D(x), v ∈ V \ C(x) を任意にとって固定する。
G' において u から v へのパスはない。
なぜなら、もしあったとすれば v には x より大きい番号がついているはず。
これは、1 回目の DFS を考えているという仮定に反する。

ゆえに、1 回目の DFS では C(x) を正しく求められていることがわかる。

帰納的に、アルゴリズムはすべての強連結成分を正しく求めることがわかる。
上記と同じ理由で、(ii) において u から v へのパスがあったとすれば、v はすでに訪問済みであることがいえる。
詳細は [2] の系 22.15 に載っている。


次のグラフ G を考えよう。


頂点 a から DFS をはじめる。
すると、次のように番号がつけられる。

※ 図では c の次に e を訪れている。 c の次に d を訪れた場合は違う番号付けになる。

逆グラフ G' は次のようになる。


G' の未訪問の頂点の中で番号が最大のものは a である。
a から DFS をはじめると、次のようになる。

この DFS で a, c, b の 3 つの頂点を訪れることができた。
これより、{a, c, b} が G の 1 つの強連結成分であることがわかる。

さらに処理を進める。
G' の未訪問の頂点の中で番号が最大のものは e である。
e から DFS をはじめると、次のようになる。

これより、{e, d, f} が G の 1 つの強連結成分であることがわかる。

ここで重要なのは、G' には辺 e → c や辺 d → c があるということである。
G' における 2 回目の DFS でこの辺を通って別の強連結成分 {a, b, c} へ進んでしまいそうだが、そのようなことは起こらない。
なぜなら、頂点 e から DFS をはじめるときには、頂点 c はすでに訪問済みだからである。

番号が最大のものを選んで DFS を進めていく限りは、いつもこの状況になっている。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。