完全グラフ

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

頂点

n

辺

\textstyle {\frac {n(n-1)}{2}}

半径

\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.

直径

\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.

概要完全グラフ, 頂点 ...

完全グラフ
7頂点の完全グラフ $K 7$
頂点	$n$
辺	$\textstyle {\frac {n(n-1)}{2}}$
半径	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
直径	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
内周	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.$
自己同型	$n! (S n)$
彩色数	$n$
彩色指数	$n$ （ $n$ が奇数） $n - 1$ （ $n$ が偶数）
特性	$(n - 1)$ -regular 対称グラフ頂点推移的辺推移的強正則整数グラフ（英語版）
表記	$K n$
テンプレートを表示

閉じる

グラフ理論は一般に、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次元空間への埋め込みが、非自明な結び目として空間に埋め込まれたハミルトン閉路を含むことも示している。