コンテンツにスキップ

完全グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
完全グラフ
K7, a complete graph with 7 vertices
頂点 n
半径
直径
内周
自己同型 n! (Sn)
彩色数 n
彩色指数 n if n is odd
n − 1 if n is even
特性 (n − 1)-regular
対称グラフ
頂点推移的
辺推移的
強正則
表記 Kn
テンプレートを表示

完全グラフ(かんぜんグラフ、: complete graph)は、任意の 2 頂点間に枝があるグラフのことを指す。 頂点の完全グラフは、で表す。また、完全グラフになる誘導部分グラフのことをクリークという[1]。サイズ のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランと言う。

幾何学的、位相幾何学的性質

[編集]

(n − 1)次元単体である。

[編集]
K1: 0 K2: 1 K3: 3 K4: 6
K5: 10 K6: 15 K7: 21 K8: 28
K9: 36 K10: 45 K11: 55 K12: 66

注釈・出典

[編集]
  1. ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

関連項目

[編集]