完全グラフ

完全グラフ
	7頂点の完全グラフK7
頂点	n
辺
半径
直径
内周
自己同型	n! (Sn)
彩色数	n
彩色指数	n（nが奇数）; n − 1（nが偶数）;
特性	(n − 1)-regular; 対称グラフ; 頂点推移的; 辺推移的; 強正則; 整数グラフ（英語版）;
表記	Kn
	テンプレートを表示

グラフ理論において完全グラフ（かんぜんグラフ、英: complete graph）は、任意の 2 頂点間に辺がある単純無向グラフである。 完全有向グラフ（英: complete digraph）は、任意の 2 頂点間に両方向へ（各方向に1つずつ）の辺がある有向グラフである^[1]。

グラフ理論は一般に、1736年のレオンハルト・オイラーによるケーニヒスベルクの七つの橋問題の研究から始まったとされる。しかし完全グラフの図示自体は、13世紀のラモン・リュイの著作の中に、正多角形の各頂点をグラフの頂点として描かれていた^[2]。このような図はmystic roseと呼ばれることもある^[3]。

性質

$n$ 頂点の完全グラフは、 $K n$ で表される。いくつかの文献は $K$ という文字がドイツ語の単語 komplett を表していると主張しているが^[4] 、完全グラフはドイツ語で vollständiger Graph であり、 $K$ という文字を含まない。他のいくつかの文献では、カジミェシュ・クラトフスキのグラフ理論への貢献を称えるものであると主張している^[5]。

$K n$ の辺数は $n (n - 1)/2$ （三角数）で、次数 $n - 1$ の正則グラフである。すべての完全グラフはそれ自身が極大クリークである。完全グラフの唯一のグラフセパレータ（英語版）は、頂点集合そのものであり、すなわち完全グラフは最大限に連結している。完全グラフの補グラフは空グラフである。

サイズ $n$ のクリークを含むグラフは「 $n$ -クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また $n$ -クリークであって、直径が $n$ 未満となるグラフを、 $n$ -クランと言う。

完全グラフの各辺に方向付け（英語版）が与えられているとき、得られる有向グラフはトーナメント（英語版）と呼ばれる。

$K n$ は、 $T i$ が $i$ 個の頂点を持つような $n$ 個の木 $T i$ に分解できる^[6]。リンゲルは、完全グラフ $K 2 n +1$ が複数個の、 $n$ 頂点の任意の木によって分解可能だと予想している^[7]。これは十分大きい $n$ に対しては真であることが知られている^[8]^[9]。

$K n +2$ の2頂点間を結ぶ異なる道の数は、次の式で求められる^[10]:

w_{n+2}=n!e_{n}=\lfloor en!\rfloor

ここで、 $e$ はネイピア数を表し、

e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.

である。

完全グラフのマッチングの数は、telephone number（英語版）である。

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... オンライン整数列大辞典の数列 A000085

この数は $n$ 頂点のグラフにおける細矢インデックスの最大値を与える^[11]。完全グラフ $K_{n}$ （ $n$ は偶数）の完全マッチングの数は、二重階乗 $(n-1)!!$ で与えられる^[12]。

完全グラフの交差数（英語版）は $K 27$ まで知られており、 $K 28$ は7233または7234個の交差を持つ。それ以上の値はRectilinear Crossing Number projectが収集している^[13]。 $K n$ の直線交差数は

0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... オンライン整数列大辞典の数列 A014540

である。

幾何学・位相幾何学との関係

$n$ 頂点完全グラフは、 $(n - 1)$ 次元単体のedge graph（英語版）である。幾何学的には、三角形の辺の集合は $K 3$ から、四角形の辺の集合は $K 4$ から得られ、以降も同様である。穿孔多面体の一つであるチャーサールの多面体（英語版）は、そのスケルトン（英語版）として $K 7$ をもつ^[15]。 4次元以上のすべてのneighborly polytope（英語版）も、完全スケルトンをもつ。

$K 1$ から $K 4$ はすべて平面的グラフである。一方、5頂点以上の完全グラフを平面に描くと必ず交差を生じる。平面的でない完全グラフである $K 5$ は、平面的グラフの特徴付けにおいて重要な役割を果たす。クラトフスキの定理によれば、グラフが平面的であるためには、部分グラフとして $K 5$ と完全2部グラフ $K 3,3$ を含まないことが必要十分であり、またワグナーの定理（英語版）によれば、グラフマイナーの場合でも同様の結果が従う。ピーターセン族（英語版）の一つとして、絡み目なし埋め込み（英語版）の禁止マイナー（英語版）として $K 6$ が同様の役割を果たしている^[16]。言いかえれば、コンウェイとゴードン^[17]が証明したように、 $K 6$ の3次元空間への埋め込みはすべて絡み目内在であり、少なくとも一つの三角形の対と絡んでいる。コンウェイとゴードンは、 $K 7$ の3次元空間への埋め込みが、非自明な結び目として空間に埋め込まれたハミルトン閉路を含むことも示している。

例

$n$ 頂点の完全グラフ（ $n$ は1から12）を、辺の数とともに以下に示す。

$K 1 : 0$	$K 2 : 1$	$K 3 : 3$	$K 4 : 6$

$K 5 : 10$	$K 6 : 15$	$K 7 : 21$	$K 8 : 28$

$K 9 : 36$	$K 10 : 45$	$K 11 : 55$	$K 12 : 66$

出典

^ Bang-Jensen, Jørgen; Gutin, Gregory (2018), “Basic Terminology, Notation and Results”, in Bang-Jensen, Jørgen; Gutin, Gregory, Classes of Directed Graphs, Springer Monographs in Mathematics, Springer International Publishing, pp. 1–34, doi:10.1007/978-3-319-71840-8_1, ISBN 978-3-319-71839-2 ; see p. 17
^ Knuth, Donald E. (2013), “Two thousand years of combinatorics”, in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 978-0191630620 .
^ Mystic Rose, nrich.maths.org, https://nrich.maths.org/6703 2012年1月23日閲覧。 .
^ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436, ISBN 0387941150 .
^ Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p. 154, ISBN 9780201308150 .
^ Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). “Optimal packings of bounded degree trees” (英語). Journal of the European Mathematical Society 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN 1435-9855. オリジナルの2020-03-09時点におけるアーカイブ。 2020年3月9日閲覧。.
^ Ringel, G. (1963). Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice.
^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). “A proof of Ringel's Conjecture”. Geometric and Functional Analysis 31 (3): 663–720. arXiv:2001.02665. doi:10.1007/s00039-021-00576-2.
^ Hartnett, Kevin (2020年2月19日). “Rainbow Proof Shows Graphs Have Uniform Parts” (英語). Quanta Magazine. 2020年2月20日時点のオリジナルよりアーカイブ。2020年2月20日閲覧。
^ Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
^ Tichy, Robert F.; Wagner, Stephan (2005), “Extremal problems for topological indices in combinatorial chemistry”, Journal of Computational Biology 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918, オリジナルの2017-09-21時点におけるアーカイブ。 2012年3月29日閲覧。 .
^ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode: 2009arXiv0906.1317C .
^ Oswin Aichholzer. “Rectilinear Crossing Number project”. 2007年4月30日時点のオリジナルよりアーカイブ。2026年1月25日閲覧。
^ Ákos Császár, A Polyhedron Without Diagonals. Archived 2017-09-18 at the Wayback Machine., Bolyai Institute, University of Szeged, 1949
^ Gardner, Martin (1988), Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, pp. 140, Bibcode: 1988ttom.book.....G, ISBN 0-7167-1924-X
^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), “Linkless embeddings of graphs in 3-space”, Bulletin of the American Mathematical Society 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR1164063 .
^ Conway, J. H.; Cameron Gordon (1983). “Knots and Links in Spatial Graphs”. Journal of Graph Theory 7 (4): 445–453. doi:10.1002/jgt.3190070410.

[1] Bang-Jensen, Jørgen; Gutin, Gregory (2018), “Basic Terminology, Notation and Results”, in Bang-Jensen, Jørgen; Gutin, Gregory, Classes of Directed Graphs, Springer Monographs in Mathematics, Springer International Publishing, pp. 1–34, doi:10.1007/978-3-319-71840-8_1, ISBN 978-3-319-71839-2 ; see p. 17

[2] Knuth, Donald E. (2013), “Two thousand years of combinatorics”, in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN 978-0191630620 .

[3] Mystic Rose, nrich.maths.org, https://nrich.maths.org/6703 2012年1月23日閲覧。 .

[4] Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 436, ISBN 0387941150 .

[5] Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, p. 154, ISBN 9780201308150 .

[6] Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). “Optimal packings of bounded degree trees” (英語). Journal of the European Mathematical Society 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN 1435-9855. オリジナルの2020-03-09時点におけるアーカイブ。 2020年3月9日閲覧。.

[7] Ringel, G. (1963). Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice.

[8] Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). “A proof of Ringel's Conjecture”. Geometric and Functional Analysis 31 (3): 663–720. arXiv:2001.02665. doi:10.1007/s00039-021-00576-2.

[9] Hartnett, Kevin (2020年2月19日). “Rainbow Proof Shows Graphs Have Uniform Parts” (英語). Quanta Magazine. 2020年2月20日時点のオリジナルよりアーカイブ。2020年2月20日閲覧。

[10] Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.

[11] Tichy, Robert F.; Wagner, Stephan (2005), “Extremal problems for topological indices in combinatorial chemistry”, Journal of Computational Biology 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918, オリジナルの2017-09-21時点におけるアーカイブ。 2012年3月29日閲覧。 .

[12] Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode: 2009arXiv0906.1317C .

[13] Oswin Aichholzer. “Rectilinear Crossing Number project”. 2007年4月30日時点のオリジナルよりアーカイブ。2026年1月25日閲覧。

[14] Ákos Császár, A Polyhedron Without Diagonals. Archived 2017-09-18 at the Wayback Machine., Bolyai Institute, University of Szeged, 1949

[15] Gardner, Martin (1988), Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, pp. 140, Bibcode: 1988ttom.book.....G, ISBN 0-7167-1924-X

[16] Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), “Linkless embeddings of graphs in 3-space”, Bulletin of the American Mathematical Society 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR1164063 .

[17] Conway, J. H.; Cameron Gordon (1983). “Knots and Links in Spatial Graphs”. Journal of Graph Theory 7 (4): 445–453. doi:10.1002/jgt.3190070410.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リストラプラシアン行列
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理最大カット問題支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ

典拠管理データベース
全般	FAST
国立図書館	ドイツアメリカイスラエル

性質

幾何学・位相幾何学との関係

例

関連項目

出典