グラフ理論において、無向グラフの連結成分（れんけつせいぶん、）とは、それ自身は連結である部分グラフであり、どのより大きな連結部分グラフにも含まれないものである。任意のグラフの連結成分はその頂点集合を素集合にし、各成分は対応する頂点部分集合による誘導部分グラフである。グラフ自身が連結である場合、成分はちょうど1つとなり、それはグラフ全体である。連結成分は連結コンポーネントと呼ばれることもある。 thumb|240px|3つの連結成分を持つグラフの例
与えられたグラフの成分数は重要なであり、マトロイド、位相空間、行列の不変量と密接に関係している。では、他の成分よりも著しく大きい単一の成分であるや、それが存在するかどうかの境界となるが頻繁に現れる現象として知られている。
グラフの連結成分は線形時間で構成でき、その特殊な問題である連結成分ラベリングは画像解析の基本技術である。動的連結性アルゴリズムは、辺の挿入・削除に応じて成分を1回あたり少ない時間で維持する。計算複雑性理論では、連結成分は限られたしか使わないアルゴリズムの研究に用いられ、準線形時間で成分数を正確に推定できることが示されている。
定義と例
与えられた無向グラフの連結成分は、どのより大きな連結部分グラフにも含まれない連結部分グラフとして定義できる。例えば最初の図に示したグラフは3つの連結成分を持つ。グラフの任意の頂点 はグラフのいずれかの連結成分に属し、その成分は から到達可能な頂点集合の誘導部分グラフとして求められる。 すべてのグラフはその連結成分たちのである。 さらに次のような特別な場合がある。 空グラフでは、各頂点が辺を1本も持たない1頂点の成分をなす。 一般には、この種の成分は任意のグラフの孤立点ごとに形成される。 連結グラフでは、成分はちょうど1つ、すなわちグラフ全体である。 森では、すべての成分は木である。 では、すべての成分は極大クリークである。この種のグラフは任意の無向グラフの推移閉包として得られ、推移閉包を求めることは連結成分を特定することと同値な定式化である。
成分のもう一つの定義は、グラフの頂点上で定義される同値関係の同値類を用いるものである。無向グラフにおいて、頂点 が頂点 から到達可能であるとは、 から への道が存在すること、あるいは同値的にウォーク（頂点と辺の繰り返しを許す道）が存在することである。到達可能性は以下のように同値関係である: 反射律: 任意の頂点から自分自身への長さ0の自明な道が存在する。 対称律: から へ道が存在するならば、同じ辺を逆順にたどることで から への道が存在する。 推移律: から への道と から への道をつなぎ合わせて、 から へのウォークを作れる。 この関係の同値類はグラフの頂点を互いに到達し合う素集合に分割する。これらの部分集合の外に追加の到達可能な頂点対は存在しない。各頂点はちょうど1つの同値類に属する。連結成分はこれらの同値類それぞれによって形成される誘導部分グラフである。 また、誘導される部分グラフではなく頂点集合そのものを成分と定義する資料もある。
同様の同値類を用いた定義は、グラフの他の種類の連結性に対する成分にも用いられており、有向グラフのや強連結成分、無向グラフの二重連結成分などがある。
成分の個数 有限グラフの成分の個数は、その全域森の辺数を数えるのに使える: 頂点 成分のグラフでは、任意の全域森はちょうど 本の辺を持つ。この数 はグラフのマトロイド論的な階数、すなわちグラフのグラフィックマトロイドの階数である。双対のコグラフマトロイドの階数はグラフの閉路階数、すなわちグラフのすべての閉路を壊すために取り除く必要のある辺の最小数に等しい。 辺、 頂点、 成分のグラフでは、閉路階数は である。
グラフは複数の仕方で位相空間として解釈できる。例えば頂点を三次元ユークリッド空間中の一般の位置の点として置き、辺をそれらの点を結ぶ線分として表すことができる。 グラフの連結成分は、こうした解釈を通して、対応する空間の位相的な連結成分へと一般化できる。これは分離できない点の同値類である。位相空間の連結成分の個数が重要な位相的不変量（第0ベッチ数）であるのと同様に、グラフの成分の個数は重要なグラフ不変量であり、位相的グラフ理論ではグラフの第0ベッチ数として解釈できる。
成分の個数はグラフ理論において他の形でも現れる。代数的グラフ理論では、有限グラフのラプラシアン行列の固有値としての 0 の重複度に等しい。 また、グラフのの最初の非零係数の次数でもあり、グラフ全体の彩色多項式はその成分たちの多項式の積として得られる。 成分数は完全マッチングを持つ有限グラフを特徴付けるタットの定理や、最大マッチングのサイズに関するタット＝ベルジュの公式、そしてグラフタフネスの定義においても重要な役割を果たす。
アルゴリズム 有限グラフの連結成分は、幅優先探索または深さ優先探索のいずれかを用いて、（頂点数と辺数に関して）線形時間で計算できる。どちらの場合も、ある特定の から始まる探索は、 を含む成分全体（かつそれだけ）を見つけてから終了する。グラフのすべての成分は頂点をループし、既に見つかった成分に含まれていない頂点に到達するたびに新たな幅優先・深さ優先探索を開始することで見つけられる。 は本質的にこのアルゴリズムを述べ、それが既に「よく知られていた」としている。
連結成分ラベリングは、コンピュータ画像解析における基本的な技術であり、画像からグラフを構成しそのグラフ上で成分解析を行うものである。頂点は画像のピクセルのうち関心のあるものや描かれた物体の一部と思われるものの部分集合であり、辺は隣接するピクセルを結ぶ。隣接性はに従う垂直方向、あるいはに従う垂直・斜め方向の両方で定義される。このグラフの連結成分を特定することで、画像のその部分のさらなる構造を調べたり、描かれている物体の種類を特定したりするための追加処理が可能になる。この種のグラフに特化した成分発見アルゴリズムが研究されており、幅優先・深さ優先探索が生成するような散在した順序ではなくピクセル順に処理できる。逐次的なピクセルアクセスがランダムアクセスより効率的な状況、例えば画像が高速なランダムアクセスを許さない階層的形式で表現されている場合や逐次アクセスがより良いメモリアクセスパターンをもたらす場合には有用である。
また、頂点や辺が追加されていくグラフの成分を動的に追跡する効率的なアルゴリズムもある。頂点の同値類への分割を素集合データ構造で管理し、それらをつなぐ辺が追加されたときに2つのクラスを併合することで実現される。これらのアルゴリズムは操作あたり償却時間 で動作する。ここで頂点と辺の追加および頂点の属する成分の判定がともに操作であり、 は急速に増大するアッカーマン関数の非常にゆっくり増大する逆関数である。 この種の増分的連結性アルゴリズムの一つの応用は最小全域木のためのクラスカル法であり、辺を長さ順に追加していき、以前に追加された部分グラフの異なる2つの成分をつなぐ場合にのみその辺を最小全域木に含める。 辺の挿入と削除の両方が許される場合は、動的連結性アルゴリズムが同じ情報を維持でき、変更あたり償却時間 および連結クエリあたり時間 で達成できるほか、ほぼ対数時間のランダム化された期待時間でも達成できる。
グラフの連結成分は、作業メモリが対数ビット数に制限され、はるかに大きな入力には読み出しアクセスしかできない（書き換え不可）チューリングマシンの能力を研究するために計算複雑性理論で用いられてきた。このように制限された機械で解ける問題は複雑性クラスを定義する。2つの頂点が同じ成分に属するかどうかを判定するという決定問題として定式化されたとき、このモデルで連結成分が求められるか否かは長年不明であったが、1982年にこの連結性問題と対数空間の下で同値な問題を含む関連する複雑性クラス が定義された。 2008年にこの連結性問題が対数空間で解けること、したがって であることが最終的に証明された。
隣接リストとして表現され頂点へランダムアクセスできるグラフでは、加法的（絶対）誤差が高々 の確率的定数保証付きで、準線形時間 で連結成分の個数を推定できる。
ランダムグラフにおける連結成分
では成分のサイズは確率変数によって与えられ、それはランダムグラフの選び方の具体的なモデルに依存する。 の 版では、 個の頂点上のグラフを、各頂点対ごとにその対を結ぶ辺を入れるかどうかを独立かつランダムに選ぶことで生成する。辺を入れる確率は 、辺なしで残す確率は である。 このモデルの連結性は に依存し、 の値域によって互いに大きく異なる3つの振る舞いが現れる。以下の解析ではすべての事象は「高確率で」起きるとする。これは十分大きな に対して事象の確率が1にいくらでも近づくことを意味する。解析は に依存しない正の定数で、0にいくらでも近づけられるパラメータ を用いる。
（亜臨界） この範囲の では、すべての成分は単純で非常に小さい。最大成分のサイズは対数的である。グラフは擬似森であり、その成分の大部分は木である: 閉路を持つ成分の頂点数は頂点数のどんな無限大に発散する関数よりもゆっくり増える。固定サイズの木は線形回数だけ現れる。 （臨界） 最大連結成分の頂点数は に比例する。他にいくつかの大きな成分が存在することもあるが、非木成分の頂点数の総和もやはり に比例する。 （超臨界） 線形個の頂点を含む単一の巨大連結成分が存在する。 が大きくなるとそのサイズはグラフ全体に近づく: ただし は方程式 の正の解である。残りの成分は小さく、サイズは対数的である。 同じランダムグラフモデルで、 という大幅に高い閾値未満では高確率で複数の連結成分が存在し、閾値を超える では単一の連結成分となる。この現象はクーポンコレクター問題と密接に関係している: グラフが連結であるためには、各頂点が少なくとも1本の辺に接続するのに十分な辺が必要である。より正確には、ランダムな辺を1本ずつグラフに追加していくとき、高確率でグラフ全体を初めて連結にする辺は最後の孤立点に接続する辺である。
格子グラフのランダム部分グラフを含む他のモデルでは、連結成分はパーコレーション理論によって記述される。この理論の鍵となる問いはの存在、すなわち巨大成分（または無限成分）が存在するかどうかの境目となる臨界確率の存在である。
脚注
; see proof of Lemma 5, p. 361
, 2.1 Sub-critical phase, pp. 20–33; see especially Theorem 2.8, p. 26, Theorem 2.9, p. 28, and Lemma 2.11, p. 29
, 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
, 2.3 Phase transition, pp. 39–45
, 4.1 Connectivity, pp. 64–68
; see Theorem 2, p. 59, and corollary, p. 65
外部リンク MATLAB code to find components in undirected graphs — MATLAB File Exchange Connected components — Steven Skiena, The Stony Brook Algorithm Repository