完全グラフのソースを表示

{{Expand English|Complete graph|date=2024年5月}}
{{infobox graph
 | name = 完全グラフ
 | image = [[Image:Complete graph K7.svg|200px]]
 | image_caption = {{math|''K''<sub>7</sub>}}, a complete graph with 7 vertices
 | vertices = {{mvar|n}}
 | radius = <math>\left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}0 & n \le 1\\ 1 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right.</math>
 | edges = <math>\textstyle\frac{n (n-1)}{2}</math>
 |notation = {{math|''K<sub>n</sub>''}}
 | automorphisms    = {{math|''n''! ([[対称群|''S'']]<sub>''n''</sub>)}}
 | chromatic_number = {{mvar|n}}
 | chromatic_index = {{mvar|n}} if {{mvar|n}} is odd<br>{{math|''n'' &minus; 1}} if {{mvar|n}} is even
 | spectrum = <math>\left\{\begin{array}{lll}\emptyset & n = 0\\\{0^1\} & n = 1\\ \{(n - 1)^1, -1^{n - 1}\} & \text{otherwise}\end{array}\right.</math><!-- is n = 1 really necessary? a partial case of the variant “otherwise”, isn’t it? -->
 | properties = [[正則グラフ|{{math|(''n'' &minus; 1)}}-regular]]<br/>[[対称グラフ]]<br/>[[頂点推移グラフ|頂点推移的]]<br/>[[辺推移グラフ|辺推移的]]<br/>[[強正則グラフ|強正則]]}}

'''完全グラフ'''（かんぜんグラフ、{{lang-en-short|complete graph}}）は、任意の 2 頂点間に枝がある[[グラフ (データ構造)|グラフ]]のことを指す。<math>n~</math> 頂点の完全グラフは、<math>K_n ~</math>で表す。また、完全グラフになる[[誘導部分グラフ]]のことを'''[[クリーク (グラフ理論)|クリーク]]'''という<ref>David Gries and Fred B. Schneider, ''A Logical Approach to Discrete Math'', Springer, 1993, p 436.</ref>。サイズ <math>n</math> のクリークを含むグラフは「''n''-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また ''n''-クリークであって、直径が ''n'' 未満となるグラフを ''n''-クランと言う。

== 幾何学的、位相幾何学的性質 ==
<math>K_n ~</math>は{{math|(''n'' &minus; 1)}}次元[[単体 (数学)|単体]]である。

== 例 ==
{|class="wikitable skin-invert-image"
! {{math|''K''<sub>1</sub>: 0}} || {{math|''K''<sub>2</sub>: 1}} || {{math|''K''<sub>3</sub>: 3}} || {{math|''K''<sub>4</sub>: 6}}
|-
| [[Image:Complete graph K1.svg|140px]]
| [[Image:Complete graph K2.svg|140px]]
| [[Image:Complete graph K3.svg|140px]]
| [[Image:3-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>5</sub>: 10}} || {{math|''K''<sub>6</sub>: 15}} || {{math|''K''<sub>7</sub>: 21}} || {{math|''K''<sub>8</sub>: 28}}
|-
| [[Image:4-simplex graph.svg|140px]]
| [[Image:5-simplex graph.svg|140px]]
| [[Image:6-simplex graph.svg|140px]]
| [[Image:7-simplex graph.svg|140px]]
|-
! {{math|''K''<sub>9</sub>: 36}} || {{math|''K''<sub>10</sub>: 45}} || {{math|''K''<sub>11</sub>: 55}} || {{math|''K''<sub>12</sub>: 66}}
|-
| [[Image:8-simplex graph.svg|140px]]
| [[Image:9-simplex graph.svg|140px]]
| [[Image:10-simplex graph.svg|140px]]
| [[Image:11-simplex graph.svg|140px]]
|}

== 注釈・出典 ==
{{reflist}}

== 関連項目 ==
* [[完全2部グラフ]]

{{Graph Theory-footer}}
{{Combin-stub}}

{{Normdaten}}
{{DEFAULTSORT:かんせんくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]