【きょうれんけつせいぶん】
強連結成分 とは？
公開:
💡 矢印に従って行って帰れる、ひとまとまり
有向グラフで、どの頂点からも互いに行き来できる頂点の最大限のまとまり。循環する依存関係を整理する際などに使う。
📌 このページのポイント
- グループ内の任意の2頂点について、両方向の経路が存在する
- 条件を保ったまま頂点を追加できない、極大な集合として分ける
- 各成分を1頂点に縮約すると、成分間のグラフに有向閉路は残らない
ひよこ 強い連結って、直接つながっていること？
ペンギン先生 直接の矢印がある必要はないよ。途中の頂点を経由してもよいので、グループ内のどの頂点からどの頂点へも到達できることが大切なんだ。矢印の向きを無視してつながるだけでは、強連結にはならないよ。
ひよこ 具体的にはどこで区切るの？
ペンギン先生 A→B→C→Aという輪があり、C→D→Eと続き、E→Dもあるとしよう。A・B・Cは互いに行き来でき、D・Eも行き来できる。でもDやEからAたちへは戻れないので、二つの成分に分かれるんだ。
ひよこ AとBだけでも行き来できるよね？
ペンギン先生 行き来できる頂点を、できるだけまとめきるのが成分だよ。この例ではCも含められるから、AとBだけを一つの成分にはしないんだ。「極大」はこれ以上付け足せないという意味で、グラフで一番大きい成分だけを選ぶという意味ではないよ。
ひよこ まとめると何が役に立つの？
ペンギン先生 成分をそれぞれ一つの頂点にすると、成分同士の関係には有向の輪がなくなるよ。もし輪があれば、その成分同士も行き来できて一つにまとまるはずだからね。循環した依存関係をひとかたまりとして、残りの順序を考えるのに役立つんだ。
もっと詳しく知りたい人へ
1頂点だけでも強連結成分ですか？
はい。長さ0の経路で自分自身へ到達できると考えるので、ほかと相互到達できない頂点は単独の成分になります。自己ループが必須ではありません。Kosaraju–Sharir法などでは、隣接リスト表現の頂点数V・辺数Eに対してO(V＋E)時間で分解できます。
まとめ：ざっくりこれだけ覚えればOK！
「強連結成分」って出てきたら「有向グラフで互いに到達できる、極大な頂点のまとまり」と思えればだいたいOK！