連結成分の基本概念
連結の定義（位相・離散の共通観点）
「連結」とは、対象の中で要素同士が途中で途切れずにつながっているという性質を扱う考え方である。位相空間では、連続な像や開集合によって分離できないという形で表現されることが多い。離散数学、とりわけグラフ理論では、辺を辿ることで到達できるかどうかが連結性の中心的な見方となる。 いずれの設定でも、直感的には「内部が分断されて見えるような切り分けができない」ことが重要になる。ただし「どのような切り分け」を許すかは文脈に依存するため、定義は位相的な分離概念と、グラフにおける経路の概念として対応づけられる。
連結成分の定義（最大性と同一視）
連結成分とは、ある対象の部分のうち「連結性を保ったまま最大に広がる塊」を指す概念である。対象全体を連結な部分に分けると考えると、各部分は互いに交わらず、全体を覆うように整理できる。
最大部分という観点
連結成分は「これ以上付け足しても連結性が崩れない」最大の部分と捉えられる。位相空間では、連結な部分集合を包含関係で比べたとき、あるものがより大きい連結部分集合に含まれていない状態が最大に相当する。グラフでは、ある頂点から辿っていける頂点の集合が実質的に最大の連結部分を与えるため、到達可能性にもとづく広がりが成分の輪郭になる。 この「最大」という性質により、成分同士は通常重ならず、対象は成分の集まりとして一意に整理される。
連結成分の一意性
成分の取り方が恣意的でないことが、連結成分という概念の実用上の価値を支える。対象に対して「連結である」という関係を満たす範囲を広げ続けると、同じ連結性の塊に到達し、結果として各要素は同一の成分に割り当てられる。 位相空間でもグラフでも、連結性は同値関係として整理でき、その同値類がそのまま連結成分になる。このため「最大性」による定義と「同値類」による定義は整合し、同じ条件の下で必ず同じ分割が得られる。
連結成分分解の直感
連結成分分解とは、対象を複数の連結成分の集まりに分ける操作と考えられる。直感的には、対象の中で移動や連続的なつながりが途切れない範囲ごとに区画を引くイメージである。 分解により、複雑な全体の性質を各成分の性質へ還元できる。たとえば「全体が連結であるか」を確かめる場合、成分が1つかどうかに帰着する。さらに、各成分を独立に調べてからまとめ直すことで解析の見通しがよくなる。
グラフにおける連結成分
グラフの連結性
グラフにおいて連結性を考えるとき、基本となるのは「経路」である。無向グラフでは、頂点間に辺を辿って到達できるなら、その頂点同士は連結であるとみなせる。この性質は成分分解の出発点になる。
到達可能性としての連結
到達可能性とは、ある頂点から出発して辺を順に辿ることで別の頂点にたどり着けるかを問う概念である。無向グラフでは辺の向きがないため、辿った経路はどちら向きにも意味を持つ。 この到達可能性が満たされる範囲が連結成分に一致し、成分内の任意の2頂点は互いに経路でつながっている。
連結ならば同じ成分に属する
グラフが（無向の文脈で）ある頂点対を連結であると判定できるなら、その2頂点は同一の連結成分に入る。逆に言えば、異なる成分に属する頂点同士は、辺を辿っても互いに到達できない。 この対応は、連結性が成分の境界を定めるという直観を形式化したものであり、成分間に経路が存在しないことを保証する。
連結成分の計算方法
連結成分分解を求める計算手順はいくつかある。典型的には、未訪問の頂点から探索を開始し、到達できる範囲を成分として切り出す方法が採用される。
深さ優先探索による分解
深さ優先探索（DFS）では、ある未訪問の頂点を起点に再帰的またはスタックを用いて深く辿る。探索中に訪れた頂点集合が、その起点に対応する連結成分になる。 アルゴリズムは、訪問済みフラグを管理しつつ、全頂点が訪問済みになるまで起点を選び直す。実装では再帰の代わりに明示的なスタックを使うことで深い再帰によるオーバーフローを回避できる。
幅優先探索による分解
幅優先探索（BFS）も同様の枠組みで使える。起点から距離（経路長）に応じて順に探索を広げ、到達できた頂点を同一成分とみなす。 DFSと比較すると探索の進み方は異なるが、到達可能集合として得られる成分の内容は一致する。BFSはキュー構造を用いるため、距離情報を同時に扱いたい場合に自然である。
Union-Find（素集合データ構造）
Union-Find（素集合、disjoint set union）は、辺を順に見ながら同じ成分に属すべき頂点の集合を統合していく手法である。初期状態では各頂点が別集合に置かれ、辺（無向）により結ばれている2頂点の集合を併合する。 最後に同じ代表元を持つ頂点が同一の連結成分に属する。経路の探索を都度行わず統合で済むため、大量の辺処理を効率よく進められることが多い。併合や検索は経路圧縮とランク（サイズ）管理といった最適化によって高速化される。
連結成分数と性質
連結成分の数や、それぞれが持つ構造は、グラフ全体の性質を把握する手がかりになる。成分数は特に「全体としてどれだけ分断されているか」を示す量として利用される。
頂点数・辺数との関係
成分ごとの頂点数と辺数は、全体のそれらを単純に足し上げることで回収できる。すなわち、連結成分分解は頂点集合を重ならない形に分割し、各成分に入る辺もまた成分内に制限される。 したがって、例えば「ある成分が木かどうか」「サイクルを含むか」といった判断は、その成分の辺と頂点の関係に現れる。
成分ごとの部分グラフの構成
各連結成分に対応する部分構造は、成分内の頂点全体と、その頂点対を結ぶ辺から成る部分グラフとして定義できる。通常、成分の境界をまたぐ辺は存在しない（存在していればそれは同一成分をまとめる要因になるため、結果として境界は崩れる）。 このため、全体グラフは連結成分ごとの部分グラフの「並び」によって記述でき、各成分を独立に解析しやすくなる。
同値関係としての定式化
同値関係（連結であること）
連結成分は「連結であること」を同値関係として捉えることで定式化できる。無向グラフなら、頂点間の連結性（経路で到達できること）は次の性質を満たす。 第一に反射性として、ある頂点は自分自身へは空の経路として到達できる。第二に対称性として、経路を辿って到達できるなら逆方向にも同じ経路を意味づけできる。第三に推移性として、Aへ到達できBへ到達できるなら、両者をつなぐ経路を合成してCへも到達できる。
同値類と連結成分の対応
この同値関係のもとで、同値類は「ある頂点から到達できる頂点全体」に一致する。したがって同値類の集合が連結成分の集合に対応する。
分割の性質（交わらない）
同値類は互いに交わらない。直感的には、ある頂点が属する連結性の広がりは一つに定まり、別の広がりと同時には整合しない。 この性質により、連結成分分解は曖昧さのない分割として扱える。
分割の網羅性（全体を覆う）
全ての頂点は何らかの同値類に属するため、同値類の集まりは頂点集合全体を完全に覆う。 結果として、連結成分分解は「漏れなく」「重複なく」構成され、各頂点は必ず一つの成分へ割り当てられる。
同値類を用いた定理の言い換え
同値類の言葉を用いると、連結性に関する主張が機械的に言い換えられる。例えば「同じ成分に属する」という表現は「同じ同値類に属する」として扱えるため、証明の骨格が整理される。 また、分解の一意性や境界の性質なども同値関係の一般論から導ける。これにより、位相空間やグラフ以外の対象でも、同様の分割原理を探す際の指針になる。
応用と周辺概念
分解後の再構成（成分グラフ）
連結成分分解の後に、各成分を一つの「塊」とみなして縮約した構造を考えることがある。これにより、元のグラフの詳細を保ったままではなく、成分間の関係の有無に焦点を当てた表現が得られる。 無向グラフでは成分間に辺がないため、縮約すると各塊が孤立した点のように見えることが多い。一方で、元が有向である場合などには成分間の到達関係が残り、より意味のある縮約図になる。
切断と連結成分の変化
連結成分は、対象に対する局所的な変更によって増減する。特に「どの要素を取り除くか」が成分の再編に直結する。
辺の削除による影響
辺を削除すると、経路の連結が失われる可能性がある。ある成分内部の経路を支えている辺がなくなると、元は一つだった成分が複数に分かれる。 逆に、冗長な経路が存在する場合には、いくつかの辺を除去しても到達可能性が保たれ、成分数が変わらないこともある。
頂点の削除による影響
頂点を取り除くと、それに付随する辺も同時に失われるため影響はさらに大きくなり得る。成分の中核となる頂点が除かれると、成分内が分断されて複数の塊に分かれる。 また、孤立した頂点が残ると新しい成分として単独の塊が現れることがある。
極めて近い概念との違い
連結成分に隣接する概念として、有向グラフの強連結成分や二部連結などがよく挙げられる。ただし、それぞれ「つながり」の定義が微妙に異なるため、成分の区分結果も一致しない。
強連結成分との対比（有向グラフ）
有向グラフでは、経路が向きに従うため、AからBへ到達できてもBからAへ到達できない場合が起こる。強連結成分は、相互に到達可能であるという条件を課し、より強い同値性に基づいて分割する。 そのため、弱連結（向きを無視した連結）を用いた成分よりも細かい分解になりやすい。
2部連結・連結度などへの橋渡し
二部連結や連結度といった概念は、「単に分かれているか」だけでなく、より強い堅牢性や分断の難しさを測る方向へ伸びていく。連結度は、いくつの要素を取り除いて初めて分断が起こるかに関心を向けるため、連結成分の枠組みから派生した評価指標とみなせる。 この橋渡しにより、分解結果だけでなく、分解がどれほど起こりにくいかという側面も扱えるようになる。
実装上の観点（計算量・データ量）
連結成分分解は、グラフの規模が大きい場面で頻出するため、計算量とメモリ消費の見積もりが重要になる。探索型（DFS/BFS）は、頂点と辺を一度ずつ程度参照するため、実装では線形に近い性能が期待できる。Union-Findは辺処理の回数に応じて計算が進み、ならし解析のもとで高速に動作する。 データ量の面では、隣接リスト形式を選ぶと疎なグラフで効率が良くなる。密なグラフでは隣接行列の扱いも検討されるが、成分数だけでなく探索の都合により最適解が変わる。実際にはグラフの疎密、メモリ上限、実行環境に応じて方式が選ばれる。