コンポーネント（グラフ理論）

グラフ理論では、無向グラフのコンポーネントは、より大きな連結サブグラフの一部ではない連結サブグラフです。グラフのコンポーネントは、その頂点を互いに素な集合に分割し、それらの集合の誘導サブグラフになります。それ自体が連結されているグラフには、グラフ全体からなるコンポーネントが 1 つだけあります。コンポーネントは連結コンポーネントと呼ばれることもあります。

与えられたグラフのコンポーネントの数は重要なグラフ不変量であり、マトロイド、位相空間、および行列の不変量と密接に関連しています。ランダム グラフでは、他のコンポーネントよりも大幅に大きい 1 つのコンポーネントである巨大コンポーネントと、それを超えると巨大コンポーネントが存在し、それ以下では巨大コンポーネントが存在しないエッジ確率である パーコレーションしきい値 の発生が 頻繁に発生する現象です。

グラフのコンポーネントは線形時間で構築でき、問題の特殊なケースである接続コンポーネントのラベリングは、画像分析の基本的な手法です。動的接続アルゴリズムは、グラフにエッジが挿入または削除されると、変更ごとに短い時間でコンポーネントを維持します。計算複雑性理論では、接続コンポーネントは空間複雑性が制限されたアルゴリズムの研究に使用されており、線形時間未満のアルゴリズムはコンポーネントの数を正確に推定できます。

与えられた無向グラフの成分は、より大きな連結部分グラフの一部ではない連結部分グラフとして定義される。例えば、最初の図に示すグラフには3つの成分がある。グラフのすべての頂点はグラフの成分の1つに属し、それはから到達可能な頂点の集合の誘導部分グラフとして見つけられる。^[1]すべてのグラフは、その成分の互いに素な和集合である。 ^[2]追加の例としては、次のような特殊なケースがある。 ${\displaystyle v}$${\displaystyle v}$

• 空のグラフでは、各頂点は1つの頂点と0つの辺を持つコンポーネントを形成します。^{[3]より一般的には、このタイプのコンポーネントは、任意のグラフ内のすべての}孤立した頂点に対して形成されます。^[4]
• 連結グラフには、グラフ全体という1つの要素が存在します。^[4]
• 森林では、あらゆる構成要素が木である。^[5]
• クラスターグラフでは、すべてのコンポーネントが最大クリークです。これらのグラフは任意の無向グラフの推移閉包として生成することができ、推移閉包を見つけることは接続されたコンポーネントを識別することと同等の定式化です。^[6]

コンポーネントの別の定義には、グラフの頂点に定義された同値関係の同値類が含まれます。無向グラフでは、から へのパス、または同等のウォーク(頂点と辺が繰り返されるパス)がある場合、頂点${\displaystyle v}$はから に到達可能です。到達可能性は同値関係です。 ${\displaystyle u}$${\displaystyle u}$ ${\displaystyle v}$

• 反射的です: 任意の頂点からその頂点自体への長さ 0 の単純なパスが存在します。
• 対称的です。 からへのパスがある場合、同じエッジを逆の順序で並べると から へのパスが形成されます。${\displaystyle u}$ ${\displaystyle v}$${\displaystyle v}$ ${\displaystyle u}$
• これは推移的です。 からへのパスと からへのパスがある場合、 2 つのパスを連結して からへのウォークを形成できます。${\displaystyle u}$ ${\displaystyle v}$${\displaystyle v}$ ${\displaystyle w}$${\displaystyle u}$ ${\displaystyle w}$

この関係の同値類は、グラフの頂点を互いに素な集合、つまり互いに到達可能な頂点の部分集合に分割し、これらの部分集合の外側には到達可能な頂点のペアは存在しない。各頂点は、正確に 1 つの同値類に属する。成分は、これらの同値類のそれぞれによって形成される誘導サブグラフである。 ^[7]また、一部の情報源では、成分を誘導するサブグラフではなく、頂点の集合として定義している。^[8]

同値類を含む同様の定義は、有向グラフの弱連結成分^[9]や強連結成分^[10]、無向グラフの双連結成分^[11]など、他の形式のグラフ連結成分を定義するためにも使用されている。

与えられた有限グラフの成分の数は、その全域森の辺の数を数えるのに使うことができる。頂点と成分を持つグラフでは、すべての全域森にはちょうど 個の辺がある。この数はグラフのマトロイド理論的ランクであり、そのグラフィックマトロイドのランクはである。双対コグラフィックマトロイドのランクはグラフの回路ランク、つまりすべてのサイクルを破るためにグラフから削除しなければならない最小の辺の数に等しい。辺、頂点、成分を持つグラフでは、回路ランクは である。^[12]${\displaystyle n}$${\displaystyle c}$${\displaystyle nc}$${\displaystyle nc}$${\displaystyle m}$${\displaystyle n}$${\displaystyle c}$${\displaystyle m-n+c}$

グラフは、頂点を3次元ユークリッド空間の一般的な位置にある点として配置し、辺をそれらの点を結ぶ線分として表すなど、複数の方法で位相空間として解釈できます。 ^[13]グラフの成分は、これらの解釈を通じて、対応する空間の位相的な連結成分として一般化できます。これらは、互いに素な閉集合のペアによって分離できない点の同値類です。位相空間の連結成分の数が重要な位相不変量、つまりゼロ次ベッティ数であるのと同様に、グラフの成分の数は重要なグラフ不変量であり、位相グラフ理論ではグラフのゼロ次ベッティ数として解釈できます。^[3]

グラフ理論では、成分の数は他の方法でも生じます。代数グラフ理論では、成分の数は有限グラフのラプラシアン行列の固有値としての 0 の重複度に等しくなります。 ^[14]また、これはグラフの彩色多項式の最初の非ゼロ係数のインデックスでもあり、グラフ全体の彩色多項式はその成分の多項式の積として得られます。 ^[15]成分の数は、完全マッチングを持つ有限グラフを特徴付けるTutte の定理^[16]や、最大マッチングのサイズに関する関連するTutte–Berge の公式^[17]、およびグラフの強靭性の定義において重要な役割を果たします。^[18]

幅優先探索または深さ優先探索のいずれかを使用して、有限グラフのコンポーネントを線形時間（グラフの頂点と辺の数に関して）で計算することは簡単です。どちらの場合も、特定の頂点から始まる探索は、戻る前に、${\displaystyle v}$それを含む${\displaystyle v}$コンポーネント全体（およびそれ以上）を見つけます。グラフのすべてのコンポーネントは、その頂点をループして見つけることができ、ループが以前に見つかったコンポーネントにまだ含まれていない頂点に到達するたびに、新しい幅優先探索または深さ優先探索を開始します。Hopcroft と Tarjan (1973) は基本的にこのアルゴリズムを説明し、それがすでに「よく知られている」と述べています。^[19]

連結成分ラベリングは、コンピュータ画像解析の基本的な手法であり、画像からグラフを構築し、グラフ上の成分解析を行う。頂点は画像のピクセルのサブセットであり、関心対象として、または描画されたオブジェクトの一部である可能性が高いものとして選択される。辺は隣接するピクセルを接続し、隣接性はフォン ノイマン近傍に従って直交的に、またはムーア近傍に従って直交および対角的に定義される。このグラフの連結成分を識別することにより、画像のそれらの部分でより多くの構造を見つけたり、どのようなオブジェクトが描画されているかを特定したりするための追加処理が可能になる。研究者らは、このタイプのグラフに特化した成分検索アルゴリズムを開発しており、幅優先または深さ優先の探索で生成されるより散在した順序ではなく、ピクセル順序で処理できる。これは、画像が高速なランダム アクセスを許可しない階層的な方法で表現されているか、または順次アクセスの方がメモリアクセス パターンに適しているなどの理由で、ピクセルへの順次アクセスがランダム アクセスよりも効率的な状況で役立つ可能性がある。^[20]

また、頂点や辺が追加されたときにグラフのコンポーネントを動的に追跡する効率的なアルゴリズムも存在する。これは、分離集合データ構造を使用して頂点の同値クラスへの分割を追跡し、2つのクラスを接続する辺が追加されたときに、任意の2つのクラスをそれらの和集合に置き換えることによって行われる。これらのアルゴリズムは、操作ごとに償却時間がかかり、頂点と辺の追加と、頂点が含まれるコンポーネントの決定はどちらも操作であり、非常に急速に増加するアッカーマン関数 の非常にゆっくりと増加する逆関数である。^[21]この種の増分接続アルゴリズムの1つの応用は、最小全域木のクラスカルのアルゴリズムであり、これは長さでソートされた順序でグラフに辺を追加し、以前に追加されたサブグラフの2つの異なるコンポーネントを接続する場合にのみ、最小全域木に辺を含めます。^[22]エッジの挿入と削除の両方が許可されている場合でも、動的接続性アルゴリズムは、変更あたりの償却時間と接続性クエリあたりの時間で、^[23]またはほぼ対数ランダム化期待時間で同じ情報を維持できます。^[24]${\displaystyle O(\alpha (n))}$${\displaystyle \alpha}$${\displaystyle O(\log ^{2}n/\log \log n)}$${\displaystyle O(\log n/\log \log n)}$

グラフのコンポーネントは、計算複雑性理論において、ワーキングメモリが対数ビットに制限され、はるかに大きな入力が変更可能ではなく読み取りアクセスでのみアクセス可能なチューリングマシンの能力を研究するために使用されてきた。このように制限されたマシンが解決できる問題は、複雑性クラスL を定義する。2つの頂点が同じコンポーネントに属しているかどうかをテストする決定問題として形式化されたときに、このモデルで接続コンポーネントが見つかるかどうかは長年不明であったが、 1982年に、この接続性の問題と、対数空間縮小の下でそれと同等の他のすべての問題を含む関連する複雑性クラスSLが定義された。^[25] 2008年にようやく、この接続性の問題が対数空間で解決できること、したがってSL = Lであることが証明された^。[26]

隣接リストとして表現されたグラフでは、その頂点にランダムアクセスすることで、一定の確率で最大で加法（絶対）誤差を得て、亜線形時間で連結成分の数を推定することができる。^[27]${\displaystyle \epsilon n}$ ${\displaystyle O(\varepsilon^{-2}\log\varepsilon^{-1})}$

ランダム グラフでは、コンポーネントのサイズはランダム変数によって与えられ、ランダム変数は、ランダム グラフの選択方法に関する特定のモデルに依存します。Erdős –Rényi–Gilbert モデルのバージョンでは、頂点のグラフは、各頂点のペアについて、そのペアを接続するエッジを含めるかどうかをランダムに独立に選択することによって生成されます。エッジを含める確率と、 2 つの頂点を接続するエッジがないままになる確率はそれぞれです。 ^[28]このモデルの接続性はに依存し、には互いに非常に異なる動作をする3 つの異なる範囲があります。以下の分析では、すべての結果が高確率 で発生します。つまり、の値が十分に大きい場合、結果の確率は 1 に任意に近くなります。分析はパラメータ に依存します。これはとは独立した正の定数で、任意に 0 に近くなることができます。 ${\displaystyle G(n,p)}$${\displaystyle n}$${\displaystyle p}$${\displaystyle 1-p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle n}$${\displaystyle \epsilon }$${\displaystyle n}$

亜臨界${\displaystyle p<(1-\varepsilon )/n}$

この範囲では、すべてのコンポーネントは単純で非常に小さい。最大のコンポーネントは対数サイズである。グラフは擬似フォレストである。そのコンポーネントのほとんどは木である。つまり、サイクルを持つコンポーネントの頂点の数は、頂点の数の無制限の関数よりもゆっくりと増加する。固定サイズのすべての木は、線形に何度も発生する。^[29]${\displaystyle p}$

致命的${\displaystyle p\approx 1/n}$

最大の連結成分の頂点数は に比例する。他にも大きな成分がいくつか存在する可能性があるが、非木成分の頂点の総数は に比例する。^[30]${\displaystyle n^{2/3}}$${\displaystyle n^{2/3}}$

超臨界${\displaystyle p>(1+\varepsilon )/n}$

頂点の線形数を含む単一の巨大な要素があります。そのサイズが大きい値の場合、グラフ全体に近づきます。ここで、は方程式の正の解です。残りの要素は小さく、対数サイズです。^[31]${\displaystyle p}$${\displaystyle |C_{1}|\おおよそ yn}$${\displaystyle y}$${\displaystyle e^{-pny}=1-y}$

ランダムグラフの同じモデルでは、がかなり高い閾値 より低い値の場合は高い確率で複数の連結成分が存在し、閾値 より高い値の場合は単一の連結成分が存在する。この現象はクーポンコレクターの問題と密接に関連している。連結されるためには、ランダムグラフには、各頂点が少なくとも1つの辺に接続されるだけの十分な辺が必要である。より正確には、ランダムな辺がグラフに1つずつ追加されると、その追加によってグラフ全体が接続される最初の辺が、最後の孤立した頂点に接する確率が高くなります。^[32]${\displaystyle p}$${\displaystyle p<(1-\varepsilon )(\log n)/n}$${\displaystyle p>(1+\varepsilon )(\log n)/n}$

グリッドグラフのランダムサブグラフを含むさまざまなモデルでは、接続されたコンポーネントはパーコレーション理論によって記述されます。この理論の重要な問題は、パーコレーションしきい値の存在です。これは、それを超えると巨大コンポーネント（または無限コンポーネント）が存在し、それ以下では存在しない臨界確率です。^[33]

• 無向グラフ内のコンポーネントを見つけるための MATLAB コード、MATLAB ファイル交換。
• 接続コンポーネント、Steven Skiena、ストーニーブルック アルゴリズム リポジトリ