コンテンツにスキップ

連結成分 (グラフ理論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』

グラフ理論において、無向グラフの連結成分（れんけつせいぶん、英: component）とは、それ自身は連結である部分グラフであり、どのより大きな連結部分グラフにも含まれないものである。任意のグラフの連結成分はその頂点集合を素集合に分割（英語版）し、各成分は対応する頂点部分集合による誘導部分グラフである。グラフ自身が連結である場合、成分はちょうど1つとなり、それはグラフ全体である。連結成分は連結コンポーネントと呼ばれることもある。

3つの連結成分を持つグラフの例

与えられたグラフの成分数は重要なグラフ不変量（英語版）であり、マトロイド、位相空間、行列の不変量と密接に関係している。ランダムグラフ（英語版）では、他の成分よりも著しく大きい単一の成分である巨大連結成分（英語版）や、それが存在するかどうかの境界となるパーコレーション閾値（英語版）が頻繁に現れる現象として知られている。

グラフの連結成分は線形時間で構成でき、その特殊な問題である連結成分ラベリングは画像解析の基本技術である。動的連結性アルゴリズムは、辺の挿入・削除に応じて成分を1回あたり少ない時間で維持する。計算複雑性理論では、連結成分は限られた空間計算量（英語版）しか使わないアルゴリズムの研究に用いられ、準線形時間で成分数を正確に推定できることが示されている。

定義と例

[編集]
7つの連結成分からなるクラスターグラフ

与えられた無向グラフの連結成分は、どのより大きな連結部分グラフにも含まれない連結部分グラフとして定義できる。例えば最初の図に示したグラフは3つの連結成分を持つ。グラフの任意の頂点 はグラフのいずれかの連結成分に属し、その成分は から到達可能な頂点集合の誘導部分グラフとして求められる[1]。 すべてのグラフはその連結成分たちの非交和（英語版）である[2]。 さらに次のような特別な場合がある。

  • 空グラフでは、各頂点が辺を1本も持たない1頂点の成分をなす[3]。 一般には、この種の成分は任意のグラフの孤立点ごとに形成される[4]。
  • 連結グラフでは、成分はちょうど1つ、すなわちグラフ全体である[4]。
  • 森では、すべての成分は木である[5]。
  • クラスターングラフ（英語版）では、すべての成分は極大クリークである。この種のグラフは任意の無向グラフの推移閉包として得られ、推移閉包を求めることは連結成分を特定することと同値な定式化である[6]。

成分のもう一つの定義は、グラフの頂点上で定義される同値関係の同値類を用いるものである。無向グラフにおいて、頂点 が頂点 から到達可能であるとは、 から への道が存在すること、あるいは同値的にウォーク（頂点と辺の繰り返しを許す道）が存在することである。到達可能性は以下のように同値関係である:

  • 反射律: 任意の頂点から自分自身への長さ0の自明な道が存在する。
  • 対称律: から へ道が存在するならば、同じ辺を逆順にたどることで から への道が存在する。
  • 推移律: から への道と から への道をつなぎ合わせて、 から へのウォークを作れる。

この関係の同値類はグラフの頂点を互いに到達し合う素集合に分割する。これらの部分集合の外に追加の到達可能な頂点対は存在しない。各頂点はちょうど1つの同値類に属する。連結成分はこれらの同値類それぞれによって形成される誘導部分グラフである[7]。 また、誘導される部分グラフではなく頂点集合そのものを成分と定義する資料もある[8]。

同様の同値類を用いた定義は、グラフの他の種類の連結性に対する成分にも用いられており、有向グラフの弱連結成分（英語版）[9]や強連結成分[10]、無向グラフの二重連結成分[11]などがある。

成分の個数

[編集]

有限グラフの成分の個数は、その全域森の辺数を数えるのに使える: 頂点 成分のグラフでは、任意の全域森はちょうど 本の辺を持つ。この数 はグラフのマトロイド論的な階数、すなわちグラフのグラフィックマトロイドの階数である。双対のコグラフマトロイドの階数はグラフの閉路階数、すなわちグラフのすべての閉路を壊すために取り除く必要のある辺の最小数に等しい。 辺、 頂点、 成分のグラフでは、閉路階数は である[12]。

グラフは複数の仕方で位相空間として解釈できる。例えば頂点を三次元ユークリッド空間中の一般の位置の点として置き、辺をそれらの点を結ぶ線分として表すことができる[13]。 グラフの連結成分は、こうした解釈を通して、対応する空間の位相的な連結成分へと一般化できる。これは分離できない点の同値類である。位相空間の連結成分の個数が重要な位相的不変量（第0ベッチ数）であるのと同様に、グラフの成分の個数は重要なグラフ不変量であり、位相的グラフ理論ではグラフの第0ベッチ数として解釈できる[3]。

成分の個数はグラフ理論において他の形でも現れる。代数的グラフ理論では、有限グラフのラプラシアン行列の固有値としての 0 の重複度に等しい[14]。 また、グラフの彩色多項式（英語版）の最初の非零係数の次数でもあり、グラフ全体の彩色多項式はその成分たちの多項式の積として得られる[15]。 成分数は完全マッチングを持つ有限グラフを特徴付けるタットの定理[16]や、最大マッチングのサイズに関するタット＝ベルジュの公式[17]、そしてグラフタフネスの定義においても重要な役割を果たす[18]。

アルゴリズム

[編集]

有限グラフの連結成分は、幅優先探索または深さ優先探索のいずれかを用いて、（頂点数と辺数に関して）線形時間で計算できる。どちらの場合も、ある特定の 頂点 から始まる探索は、 を含む成分全体（かつそれだけ）を見つけてから終了する。グラフのすべての成分は頂点をループし、既に見つかった成分に含まれていない頂点に到達するたびに新たな幅優先・深さ優先探索を開始することで見つけられる。Hopcroft & Tarjan (1973) は本質的にこのアルゴリズムを述べ、それが既に「よく知られていた」としている[19]。

連結成分ラベリングは、コンピュータ画像解析における基本的な技術であり、画像からグラフを構成しそのグラフ上で成分解析を行うものである。頂点は画像のピクセルのうち関心のあるものや描かれた物体の一部と思われるものの部分集合であり、辺は隣接するピクセルを結ぶ。隣接性はフォン・ノイマン近傍（英語版）に従う垂直方向、あるいはムーア近傍（英語版）に従う垂直・斜め方向の両方で定義される。このグラフの連結成分を特定することで、画像のその部分のさらなる構造を調べたり、描かれている物体の種類を特定したりするための追加処理が可能になる。この種のグラフに特化した成分発見アルゴリズムが研究されており、幅優先・深さ優先探索が生成するような散在した順序ではなくピクセル順に処理できる。逐次的なピクセルアクセスがランダムアクセスより効率的な状況、例えば画像が高速なランダムアクセスを許さない階層的形式で表現されている場合や逐次アクセスがより良いメモリアクセスパターンをもたらす場合には有用である[20]。

また、頂点や辺が追加されていくグラフの成分を動的に追跡する効率的なアルゴリズムもある。頂点の同値類への分割を素集合データ構造で管理し、それらをつなぐ辺が追加されたときに2つのクラスを併合することで実現される。これらのアルゴリズムは操作あたり償却時間 で動作する。ここで頂点と辺の追加および頂点の属する成分の判定がともに操作であり、 は急速に増大するアッカーマン関数の非常にゆっくり増大する逆関数である[21]。 この種の増分的連結性アルゴリズムの一つの応用は最小全域木のためのクラスカル法であり、辺を長さ順に追加していき、以前に追加された部分グラフの異なる2つの成分をつなぐ場合にのみその辺を最小全域木に含める[22]。 辺の挿入と削除の両方が許される場合は、動的連結性アルゴリズムが同じ情報を維持でき、変更あたり償却時間 および連結クエリあたり時間 で達成できる[23]ほか、ほぼ対数時間のランダム化された期待時間でも達成できる[24]。

グラフの連結成分は、作業メモリが対数ビット数に制限され、はるかに大きな入力には読み出しアクセスしかできない（書き換え不可）チューリングマシンの能力を研究するために計算複雑性理論で用いられてきた。このように制限された機械で解ける問題は複雑性クラスL（英語版）を定義する。2つの頂点が同じ成分に属するかどうかを判定するという決定問題として定式化されたとき、このモデルで連結成分が求められるか否かは長年不明であったが、1982年にこの連結性問題と対数空間還元（英語版）の下で同値な問題を含む関連する複雑性クラス SL（英語版） が定義された[25]。 2008年にこの連結性問題が対数空間で解けること、したがって SL = L であることが最終的に証明された[26]。

隣接リストとして表現され頂点へランダムアクセスできるグラフでは、加法的（絶対）誤差が高々 の確率的定数保証付きで、準線形時間 で連結成分の個数を推定できる[27]。

ランダムグラフにおける連結成分

[編集]
→詳細は「巨大連結成分」を参照
辺確率 （臨界範囲）の1000頂点エルデシュ＝レーニィ＝ギルバートランダムグラフ。大きな成分と多くの小さな成分が見える

ランダムグラフ（英語版）では成分のサイズは確率変数によって与えられ、それはランダムグラフの選び方の具体的なモデルに依存する。 エルデシュ＝レーニィ＝ギルバートモデル（英語版）の 版では、 個の頂点上のグラフを、各頂点対ごとにその対を結ぶ辺を入れるかどうかを独立かつランダムに選ぶことで生成する。辺を入れる確率は 、辺なしで残す確率は である[28]。 このモデルの連結性は に依存し、 の値域によって互いに大きく異なる3つの振る舞いが現れる。以下の解析ではすべての事象は「高確率で」起きるとする。これは十分大きな に対して事象の確率が1にいくらでも近づくことを意味する。解析は に依存しない正の定数で、0にいくらでも近づけられるパラメータ を用いる。

（亜臨界）
この範囲の では、すべての成分は単純で非常に小さい。最大成分のサイズは対数的である。グラフは擬似森であり、その成分の大部分は木である: 閉路を持つ成分の頂点数は頂点数のどんな無限大に発散する関数よりもゆっくり増える。固定サイズの木は線形回数だけ現れる[29]。
（臨界）
最大連結成分の頂点数は に比例する。他にいくつかの大きな成分が存在することもあるが、非木成分の頂点数の総和もやはり に比例する[30]。
（超臨界）
線形個の頂点を含む単一の巨大連結成分が存在する。 が大きくなるとそのサイズはグラフ全体に近づく: ただし は方程式 の正の解である。残りの成分は小さく、サイズは対数的である[31]。

同じランダムグラフモデルで、 という大幅に高い閾値未満では高確率で複数の連結成分が存在し、閾値を超える では単一の連結成分となる。この現象はクーポンコレクター問題と密接に関係している: グラフが連結であるためには、各頂点が少なくとも1本の辺に接続するのに十分な辺が必要である。より正確には、ランダムな辺を1本ずつグラフに追加していくとき、高確率でグラフ全体を初めて連結にする辺は最後の孤立点に接続する辺である[32]。

格子グラフのランダム部分グラフを含む他のモデルでは、連結成分はパーコレーション理論によって記述される。この理論の鍵となる問いはパーコレーション閾値（英語版）の存在、すなわち巨大成分（または無限成分）が存在するかどうかの境目となる臨界確率の存在である[33]。

脚注

[編集]
  1. ↑ Clark, John; Holton, Derek Allan (1995), A First Look at Graph Theory, Allied Publishers, p. 28, ISBN 9788170234630, オリジナルの2022-01-08時点におけるアーカイブ。 2022年1月7日閲覧。
  2. ↑ Joyner, David; Nguyen, Minh Van; Phillips, David (May 10, 2013), “1.6.1 Union, intersection, and join”, Algorithmic Graph Theory and Sage (0.8-r1991 ed.), Google, pp. 34–35, オリジナルのJanuary 16, 2016時点におけるアーカイブ。 2022年1月8日閲覧。
  3. 1 2 Tutte, W. T. (1984), Graph Theory, Encyclopedia of Mathematics and its Applications, 21, Reading, Massachusetts: Addison-Wesley, p. 15, ISBN 0-201-13520-5, MR 0746795, オリジナルの2022-01-07時点におけるアーカイブ。 2022年1月7日閲覧。
  4. 1 2 Thulasiraman, K.; Swamy, M. N. S. (2011), Graphs: Theory and Algorithms, John Wiley & Sons, p. 9, ISBN 978-1-118-03025-7, オリジナルの2022-01-07時点におけるアーカイブ。 2022年1月7日閲覧。
  5. ↑ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290, オリジナルの2022-01-08時点におけるアーカイブ。 2022年1月8日閲覧。
  6. ↑ McColl, W. F.; Noshita, K. (1986), “On the number of edges in the transitive closure of a graph”, Discrete Applied Mathematics（英語版） 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101
  7. ↑ Foldes, Stephan (2011), Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons, p. 199, ISBN 978-1-118-03143-8, オリジナルの2022-01-07時点におけるアーカイブ。 2022年1月7日閲覧。
  8. ↑ Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew (2001), “7.1 Connected components: Definitions”, The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, pp. 97–98
  9. ↑ Knuth, Donald E. (January 15, 2022), “Weak components”, The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal, pp. 11–14, オリジナルのJanuary 18, 2022時点におけるアーカイブ。 2022年3月1日閲覧。
  10. ↑ Lewis, Harry; Zax, Rachel (2019), Essential Discrete Mathematics for Computer Science, Princeton University Press, p. 145, ISBN 978-0-691-19061-7, オリジナルの2022-01-08時点におけるアーカイブ。 2022年1月8日閲覧。
  11. ↑ Kozen, Dexter C. (1992), “4.1 Biconnected components”, The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, New York: Springer-Verlag, pp. 20–22, doi:10.1007/978-1-4612-4400-4, ISBN 0-387-97687-6, MR 1139767, オリジナルの2022-01-08時点におけるアーカイブ。 2022年1月8日閲覧。
  12. ↑ Wilson, R. J. (1973), “An introduction to matroid theory”, The American Mathematical Monthly（英語版） 80 (5): 500–525, doi:10.1080/00029890.1973.11993318, JSTOR 2319608, MR 0371694
  13. ↑ Wood, David R. (2014), “Three-dimensional graph drawing”, in Kao, Ming-Yang, Encyclopedia of Algorithms, Springer, pp. 1–7, doi:10.1007/978-3-642-27848-8_656-1, ISBN 978-3-642-27848-8, オリジナルの2022-01-08時点におけるアーカイブ。 2022年1月8日閲覧。
  14. ↑ Cioabă, Sebastian M. (2011), “Some applications of eigenvalues of graphs”, in Dehmer, Matthias, Structural Analysis of Complex Networks, New York: Birkhäuser/Springer, pp. 357–379, doi:10.1007/978-0-8176-4789-6_14, ISBN 978-0-8176-4788-9, MR 2777924; see proof of Lemma 5, p. 361 Archived 2022-01-08 at the Wayback Machine.
  15. ↑ Read, Ronald C. (1968), “An introduction to chromatic polynomials”, Journal of Combinatorial Theory（英語版） 4: 52–71, doi:10.1016/S0021-9800(68)80087-0, MR 0224505; see Theorem 2, p. 59, and corollary, p. 65
  16. ↑ Tutte, W. T. (1947), “The factorization of linear graphs”, The Journal of the London Mathematical Society（英語版） 22 (2): 107–111, doi:10.1112/jlms/s1-22.2.107, MR 0023048
  17. ↑ Berge, Claude (1958), “Sur le couplage maximum d'un graphe”, Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences（英語版） 247: 258–259, MR 0100850
  18. ↑ Chvátal, Václav (1973), “Tough graphs and Hamiltonian circuits”, Discrete Mathematics（英語版） 5 (3): 215–228, doi:10.1016/0012-365X(73)90138-6, MR 0316301
  19. ↑ Hopcroft, John; Tarjan, Robert (June 1973), “Algorithm 447: efficient algorithms for graph manipulation”, Communications of the ACM 16 (6): 372–378, doi:10.1145/362248.362272
  20. ↑ Dillencourt, Michael B.; Samet, Hanan; Tamminen, Markku (1992), “A general approach to connected-component labeling for arbitrary image representations”, Journal of the ACM 39 (2): 253–280, doi:10.1145/128749.128750, MR 1160258
  21. ↑ Bengelloun, Safwan Abdelmajid (December 1982), Aspects of Incremental Computing (PhD thesis), Yale University, p. 12, ProQuest 303248045
  22. ↑ Skiena, Steven (2008), “6.1.2 Kruskal's Algorithm”, The Algorithm Design Manual, Springer, pp. 196–198, Bibcode:2008adm..book.....S, doi:10.1007/978-1-84800-070-4, ISBN 978-1-84800-069-8, オリジナルの2022-01-07時点におけるアーカイブ。 2022年1月7日閲覧。
  23. ↑ Wulff-Nilsen, Christian (2013), “Faster deterministic fully-dynamic graph connectivity”, in Khanna, Sanjeev, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 1757–1769, arXiv:1209.5608, doi:10.1137/1.9781611973105.126, ISBN 978-1-61197-251-1
  24. ↑ Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), “Fully dynamic connectivity in amortized expected time”, in Klein, Philip N., Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 510–520, arXiv:1609.05867, doi:10.1137/1.9781611974782.32
  25. ↑ Lewis, Harry R.; Papadimitriou, Christos H. (1982), “Symmetric space-bounded computation”, Theoretical Computer Science（英語版） 19 (2): 161–187, doi:10.1016/0304-3975(82)90058-5, MR 0666539
  26. ↑ Reingold, Omer (2008), “Undirected connectivity in log-space”, Journal of the ACM 55 (4): A17:1–A17:24, doi:10.1145/1391289.1391291, MR 2445014
  27. ↑ Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik (2014), “Estimating the number of connected components in sublinear time”, Information Processing Letters（英語版） 114 (11): 639–642, doi:10.1016/j.ipl.2014.05.008, MR 3230913
  28. ↑ Frieze, Alan; Karoński, Michał (2016), “1.1 Models and relationships”, Introduction to Random Graphs, Cambridge University Press, Cambridge, pp. 3–9, doi:10.1017/CBO9781316339831, ISBN 978-1-107-11850-8, MR 3675279
  29. ↑ Frieze & Karoński (2016), 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
  30. ↑ Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45
  31. ↑ Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
  32. ↑ Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68
  33. ↑ Cohen, Reuven; Havlin, Shlomo (2010), “10.1 Percolation on complex networks: Introduction”, Complex Networks: Structure, Robustness and Function, Cambridge University Press, pp. 97–98, ISBN 978-1-139-48927-0, オリジナルの2022-01-10時点におけるアーカイブ。 2022年1月10日閲覧。

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=連結成分_(グラフ理論)&oldid=110881005」から取得