コンテンツにスキップ
Wikipedia

完全グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月)
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
  • 英語版記事を日本語へ機械翻訳したバージョン(Google翻訳)。
  • 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
  • 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
  • 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
  • 翻訳後、{{翻訳告知|en|Complete graph|...}}をノートに追加することもできます。
  • Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
完全グラフ
K7, a complete graph with 7 vertices
頂点 n
辺 n ( n − 1 ) 2 {\displaystyle \textstyle {\frac {n(n-1)}{2}}} {\displaystyle \textstyle {\frac {n(n-1)}{2}}}
半径 { 0 n ≤ 1 1 otherwise {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\1円&{\text{otherwise}}\end{array}}\right.} {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\1円&{\text{otherwise}}\end{array}}\right.}
直径 { 0 n ≤ 1 1 otherwise {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\1円&{\text{otherwise}}\end{array}}\right.} {\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\1円&{\text{otherwise}}\end{array}}\right.}
内周 { ∞ n ≤ 2 3 otherwise {\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\3円&{\text{otherwise}}\end{array}}\right.} {\displaystyle \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
対称グラフ
頂点推移的
辺推移的
強正則
表記 Kn
テンプレートを表示

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

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

[編集 ]

K n   {\displaystyle K_{n}~} {\displaystyle K_{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.

関連項目

[編集 ]
要素・定義・表現
指標
部分構造
全体構造
固有名を持つグラフ
トピック・定理
カテゴリ カテゴリ / コモンズ コモンズ

AltStyle によって変換されたページ (->オリジナル) /