グラフ理論において完全グラフ（かんぜんグラフ、）は、任意の 2 頂点間に辺がある単純無向グラフである。 完全有向グラフ（）は、任意の 2 頂点間に両方向へ（各方向に1つずつ）の辺がある有向グラフである; see p. 17。
グラフ理論は一般に、1736年のレオンハルト・オイラーによるケーニヒスベルクの七つの橋問題の研究から始まったとされる。しかし完全グラフの図示自体は、13世紀のラモン・リュイの著作の中に、正多角形の各頂点をグラフの頂点として描かれていた.。このような図はmystic roseと呼ばれることもある.。
性質
頂点の完全グラフは、で表される。いくつかの文献はという文字がドイツ語の単語 を表していると主張しているが. 、完全グラフはドイツ語で であり、という文字を含まない。 他のいくつかの文献では、カジミェシュ・クラトフスキのグラフ理論への貢献を称えるものであると主張している.。
の辺数は（三角数）で、次数の正則グラフである。 すべての完全グラフはそれ自身が極大クリークである。 完全グラフの唯一のは、頂点集合そのものであり、すなわち完全グラフは最大限に連結している。 完全グラフの補グラフは空グラフである。
サイズのクリークを含むグラフは「-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また -クリークであって、直径が未満となるグラフを、-クランと言う。
完全グラフの各辺にが与えられているとき、得られる有向グラフはと呼ばれる。
は、 が個の頂点を持つような個の木 に分解できる。 リンゲルは、完全グラフが複数個の、頂点の任意の木によって分解可能だと予想している。 これは十分大きいに対しては真であることが知られている。
の2頂点間を結ぶ異なる道の数は、次の式で求められるHassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.:
ここで、はネイピア数を表し、
である。
完全グラフのマッチングの数は 、である。 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ...
この数は頂点のグラフにおける細矢インデックスの最大値を与える.。 完全グラフ（は偶数）の完全マッチングの数は、二重階乗で与えられる.。
完全グラフのはまで知られており、は7233または7234個の交差を持つ。それ以上の値はRectilinear Crossing Number projectが収集している。 の直線交差数は 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, ... である。
幾何学・位相幾何学との関係
頂点完全グラフは、次元単体のである。 幾何学的には、三角形の辺の集合はから、四角形の辺の集合はから得られ、以降も同様である。 穿孔多面体の一つであるは、そのとしてをもつ。 4次元以上のすべてのも、完全スケルトンをもつ。
からはすべて平面的グラフである。 一方、5頂点以上の完全グラフを平面に描くと必ず交差を生じる。 平面的でない完全グラフであるは、平面的グラフの特徴付けにおいて重要な役割を果たす。 クラトフスキの定理によれば、グラフが平面的であるためには、部分グラフとしてと完全2部グラフを含まないことが必要十分であり、またによれば、グラフマイナーの場合でも同様の結果が従う。 の一つとして、のとしてが同様の役割を果たしている.。 言いかえれば、コンウェイとゴードンが証明したように、の3次元空間への埋め込みはすべて絡み目内在であり、少なくとも一つの三角形の対と絡んでいる。 コンウェイとゴードンは、の3次元空間への埋め込みが、非自明な結び目として空間に埋め込まれたハミルトン閉路を含むことも示している。
例 頂点の完全グラフ（は1から12）を、辺の数とともに以下に示す。
関連項目 フルコネクトネットワーク - コンピュータネットワークにおける例 完全2部グラフ - 2部グラフで、一方の頂点集合の各頂点から、もう一方の頂点集合のすべての頂点へと辺が伸びているもの 単体 (数学) - を単体の次元として、頂点の完全グラフと同一視できる
出典