完全グラフ

完全グラフ
	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 頂点間に枝があるグラフのことを指す。 $n~$ 頂点の完全グラフは、 $K_{n}~$ で表す。また、完全グラフになる誘導部分グラフのことをクリークという^[1]。サイズ $n$ のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランと言う。

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

$K_{n}~$ は $(n - 1)$ 次元単体である。

例編集

$K 1 : 0$	$K 2 : 1$	$K 3 : 3$	$K 4 : 6$

$K 5 : 10$	$K 6 : 15$	$K 7 : 21$	$K 8 : 28$

$K 9 : 36$	$K 10 : 45$	$K 11 : 55$	$K 12 : 66$

注釈・出典編集

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

完全グラフ

目次

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

例編集

注釈・出典編集

関連項目編集

完全グラフ
$K 7$ , a complete graph with 7 vertices
頂点	$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$ if $n$ is odd $n - 1$ if $n$ is even
特性	$(n - 1)$ -regular 対称グラフ頂点推移的辺推移的強正則
表記	$K n$
テンプレートを表示

完全グラフ

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

例 編集

注釈・出典 編集

関連項目 編集

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

例編集

注釈・出典編集

関連項目編集