連結成分は、無向グラフで線をたどって互いに行き来できる、これ以上広げられない点のまとまりです。近くに描かれた点の集まりでも、直接つながる点だけの集まりでもありません。
直接つながらなくても、同じまとまり
A–B、B–C、D–Eの三本の線があるとします。AとCは直接の線を持ちませんが、Bを経由して行き来できるので同じ連結成分です。まとまりは{A,B,C}と{D,E}の二つになります。
A ─ B ─ C D ─ E 成分1：A B C 成分2：D E
{A,B}だけを成分と呼ばないのは、Cも加えられるからです。「最大」とは人数が全体で一番多いという意味ではなく、そのまとまりに、さらに到達できる点を足せないという意味です。孤立した点も、それだけで一つの連結成分になります。
一本追加・一本削除するとどう変わる？
上の模型にC–Dを追加すると、すべてがつながり成分は一つになります。そのC–Dを再び外すと二つに戻ります。削除によって成分数が増える辺を「橋」と呼びます。
| 操作 | 成分数 | 理由 |
|---|---|---|
| 元のAB・BC・DE | 2 | ABCとDEが分かれる |
| CDを追加 | 1 | 二つのまとまりが接続する |
| さらにACを追加 | 1 | すでにつながる内部の迂回路が増える |
| その後ABを削除 | 1 | AはC経由でBへ行ける |
橋かどうかは、その辺だけの性質ではなく、ほかの辺を含む構造で決まります。図で長く描かれた辺が必ず橋になるわけでもありません。
向きがある場合は、別の定義が必要
A→B→Cという矢印なら、AからCには行けますがCからAには戻れません。向きを無視すれば一つに見えても、相互に到達できるとは言えません。
有向グラフでは、互いに到達できる強連結と、向きを無視した弱連結などを区別します。サイトのリンクを調べる場合も、ページAがBへリンクしているだけで、BからAへの道があるとは限りません。
ブログの孤立記事を考える例
記事を点、記事中のリンクを線にした模型なら、つながりの点検に使えます。ただし実際のサイトはメニュー、カテゴリー、検索などからも読めます。本文リンクだけのグラフで孤立した点を見つけても、検索エンジンに絶対に発見されないとまでは言えません。
何をリンクとして数えたかを記録した上で、入口や戻り道を整えるのが実用的です。中心性と最短経路も、同じ点と線から別の問いを考える方法です。