完全なグラフ

完全なグラフ
K 7、7つの頂点を持つ完全グラフ
頂点	ん
エッジ	${\displaystyle \textstyle {\frac {n(n-1)}{2}}}$
半径	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
直径	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
胴回り	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
自己同型	n ! ( S n )
彩度数	ん
色指数	nが奇数の場合はn nが偶数の場合はn − 1
スペクトラム	${\displaystyle \left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{otherwise}}\end{array}}\right.}$
プロパティ	( n − 1) -正規 対称グラフ 頂点推移 エッジ推移 強い規則性 積分
表記	けーん​
グラフとパラメータの表

数学のグラフ理論の分野において、完全グラフとは、異なる頂点のペアがすべて一意の辺で接続されている単純な 無向グラフです。完全有向グラフとは、異なる頂点のペアがすべて一意の辺のペア（各方向に1つ）で接続されている有向グラフです。 ^[1]

グラフ理論自体は、レオンハルト・オイラーが1736年に書いた「ケーニヒスベルクの七つの橋」に始まると一般的に考えられている。しかし、頂点が正多角形の点に置かれた完全グラフの図は、すでに13世紀のラモン・リュイの著作の中に登場していた。^{[2]このような図は、}神秘のバラと呼ばれることもある。^[3]

n頂点の完全グラフはK _nと表記される。一部の文献では、この表記法の文字K はドイツ語のkomplettを表していると主張しているが^[4]、完全グラフのドイツ語名vollständiger Graphには文字K は含まれておらず、他の文献ではこの表記法はグラフ理論へのカジミエシュ・クラトフスキの貢献を称えるものであると述べている^{[5] 。}

K _{n は}n ( n – 1)/2 の辺（三角数）を持ち、次数n – 1の正則グラフです。すべての完全グラフはそれ自身の最大クリークです。グラフを切断する唯一の頂点カットは頂点の完全集合であるため、それらは最大連結です。完全グラフの補グラフは空グラフです。

完全グラフの辺にそれぞれ方向が与えられている場合、結果として得られる有向グラフはトーナメントと呼ばれます。

K _{n は}、 i 個の頂点を持つ n_本のツリーT iに分解_できます。^[6]リンゲルの予想は、完全グラフK _{2 n +1}がn個の辺を持つ任意のツリーのコピーに分解できるかどうかを尋ねています。^{[7]これは、十分に大きい}nに対して真であることが知られています。^{[8] [9]}

K _{n +2}における特定の頂点間の異なる経路の数は^[10]で 与えられる。

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

ここでeはオイラー定数であり、

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

完全グラフのマッチング数は電話番号によって与えられる。

1、1、2、4、10、26、76、232、764、2620、9496、35696、140152、568504、2390480、10349536、46206736、...（OEISのシーケンスA000085）。

これらの数字は、 n頂点グラフの細谷指数の最大値を与える。^[11]完全グラフKn（nは偶数）の完全マッチングの_数は、二重階乗（n -1）で与えられる。^[12]

K ₂₇までの交差数は分かっており、K ₂₈では7233または7234の交差が必要となる。それ以上の値は、Rectilinear Crossing Numberプロジェクトによって収集されている。^[13] K _nのRectilinear Crossing Numberは以下のとおりである。

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、...（OEISのシーケンスA014540 ）。

n個のノードを持つ完全グラフは、( n -1)単体の辺を表します。幾何学的には、K _{3 は}三角形の辺集合を形成し、K _{4 は}四面体などの辺集合を形成します。トーラスの位相を持つ非凸多面体であるCsászár多面体は、完全グラフK _{7 を}その骨格として持っています。^[15] 4 次元以上の すべての隣接多面体も完全な骨格を持っています。

K ₁からK ₄はすべて平面グラフです。ただし、5 つ以上の頂点を持つ完全グラフのすべての平面描画には交差が含まれている必要があり、非平面完全グラフK ₅は平面グラフの特徴付けで重要な役割を果たします。クラトフスキーの定理により、グラフが平面であるためには、 K ₅も完全二部グラフ K _3,3も部分分割として含まれず、ワグナーの定理により、部分分割の代わりにグラフマイナーに対しても同じ結果が成り立ちます。ピーターセンファミリーの一部として、 K _{6 は}リンクなし埋め込みの禁制マイナーの 1 つとして同様の役割を果たします。 ^[16]言い換えると、コンウェイとゴードン^{[17]が証明したように、3 次元空間への}K ₆のすべての埋め込みは、少なくとも 1 組のリンクされた三角形で本質的にリンクされています。コンウェイとゴードンはまた、 K ₇の任意の 3 次元埋め込みには、非自明な結び目として空間に埋め込まれたハミルトンサイクルが含まれている。

1 から 12 までの頂点の完全グラフと辺の数を以下に示します。 ${\displaystyle n}$${\displaystyle n}$

• コンピュータネットワークにおける完全接続ネットワーク
• 完全二部グラフ（または二クリーク）は、二部グラフの片側のすべての頂点が反対側のすべての頂点に接続されている特殊な二部グラフです。
• 単体は頂点の完全グラフと同一であり、 は単体の次元です。${\displaystyle n+1}$${\displaystyle n}$

ウィキメディア・コモンズには、完全グラフに関連するメディアがあります。

無料辞書のウィクショナリーで「完全グラフ」を調べてください。

• Weisstein、Eric W.「完全グラフ」。MathWorld。