完全グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
完全グラフ
Complete graph K7.svg
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
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg

脚注[編集]

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

関連項目[編集]