完全グラフ - Wikipedia

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）

翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。
万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
翻訳後、{{翻訳告知|en|Complete graph|…}}をノートに追加することもできます。
Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

完全グラフ
$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$
テンプレートを表示

完全グラフ（かんぜんグラフ、英: 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.

関連項目

[編集]

完全2部グラフ

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リスト
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合（英語版）マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

典拠管理データベース
全般	FAST
国立図書館	ドイツイスラエルアメリカ