クネーザーグラフとは - わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

クネーザーグラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 10:00 UTC 版)

クネーザーグラフ
クネーザーグラフ $KG 5,2$ （ピーターセングラフと同型）
命名者	マルティン・クネーザー
頂点	$\textstyle {\binom {n}{k}}$
辺	$\textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2$
彩色数	$\left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.$
特性	$\textstyle {\binom {n-k}{k}}$ -正則弧推移的
表記	$KG n, k$ , $K (n, k)$
テンプレートを表示

数学のグラフ理論におけるクネーザーグラフ（英: Kneser graph） $KG n, k$ とは、n 元集合のk元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究したマルティン・クネーザーの名にちなむ。

例

n 個の頂点を持つ完全グラフはクネーザーグラフ $KG n,1$ である。

クネーザーグラフ $KG 2 n - 1, n - 1$ は奇グラフ（英語版） $O n$ として知られる。奇グラフ $O 3 = KG 5,2$ はピーターセングラフと同型である。

性質

クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず $\textstyle {\binom {n-k}{k}}$ 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。

Kneser (1955)が予想したように、クネーザーグラフ $KG n, k$ の彩色数は必ず $n - 2 k + 2$ となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。László Lovász (1978) はこの事実を、位相的組合せ論（英語版）の分野における位相的手法を用いることによって証明した。その後まもなく、Imre Bárány (1978) はボルサック-ウラムの定理（英語版）とデヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらに Greene (2002) は簡略化ではあるが依然として位相的な証明を与えることによってモーガン賞（英語版）を得た。また、Matoušek (2004) は純粋な組合せ論的証明（英語版）を与えた。
$n \geq 3 k$ であるなら、クネーザーグラフは常にハミルトン閉路を含む (Chen 2000)。計算機的な研究によれば、 $n \leq 27$ であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである (Shields 2004)。
$n < 3 k$ であるなら、クネーザーグラフは三角形を含まない。より一般的に、 $n \geq 2 k + 2$ であればクネーザーグラフは常に長さ4の閉路を含むが、 $2 k$ に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがある (Denley 1997)。
連結クネーザーグラフ $KG n, k$ の直径 (distance (graph theory)) は
$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1$ (Valencia-Pabon & Vera 2005)