クネーザーグラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
クネーザーグラフ
Kneser graph KG(5,2).svg
クネーザーグラフ KG5,2
ピーターセングラフと同型)
命名者 マルティン・クネーザー
頂点
彩色数
特性 -正則
弧推移的
表記 KGn,k, K(n,k)
テンプレートを表示

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

[編集]

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

クネーザーグラフ KG2n − 1,n − 1奇グラフ英語版 On として知られる。奇グラフ O3 = KG5,2ピーターセングラフと同型である。

性質[編集]

  • クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。
  • Kneser (1955)が予想したように、クネーザーグラフ KGn,k彩色数は必ず n − 2k + 2 となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。László Lovász (1978) はこの事実を、位相的組合せ論英語版の分野における位相的手法を用いることによって証明した。その後まもなく、Imre Bárány (1978)ボルサック-ウラムの定理英語版デヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらに Greene (2002) は簡略化ではあるが依然として位相的な証明を与えることによってモーガン賞英語版を得た。また、Matoušek (2004) は純粋な組合せ論的証明英語版を与えた。
  • n ≥ 3k であるなら、クネーザーグラフは常にハミルトン閉路を含む (Chen 2000)。計算機的な研究によれば、n ≤ 27 であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである (Shields 2004)。
  • n < 3kであるなら、クネーザーグラフは三角形を含まない。より一般的に、n ≥ 2k + 2 であればクネーザーグラフは常に長さ4の閉路を含むが、2k に近い値 n に対して、最も短い奇閉路は一定の長さを持たないことがある (Denley 1997)。
  • 連結クネーザーグラフ KGn,k直径 (distance (graph theory)
    (Valencia-Pabon & Vera 2005)
である。
  • クネーザーグラフ KGn,kグラフスペクトル英語版は次のように与えられる:
に対し、固有値 が得られる。ここで、その重複度は、 に対しては であり、 に対しては 1 となる。証明にはこの論文を参照されたい。

関連するグラフ[編集]

ジョンソングラフ英語版は、n 元集合の k 元部分集合が頂点となり、その (k − 1)-元部分集合が一致するとき、各頂点が隣接するようなグラフである。k = 2 に対して、ジョンソングラフはクネーザーグラフ KGn,2となる。ジョンソングラフは、ジョンソンスキーム英語版と密接に関係している。それらはいずれもセルマー・ジョンソン英語版の名にちなむ。

一般化クネーザーグラフ KGn,k,s とは、クネーザーグラフと頂点集合は同じものであるが、二つの頂点が連結するための必要十分条件が、それらに対応する集合が s 以下の共通部分を持つこと、であるようなグラフのことである (Denley 1997)。したがって、KGn,k,0 = KGn,k である。

2部クネーザーグラフ (bipartite Kneser graph)Hn,k は、n 個の元の集まりから抽出される k 個の元および nk 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 でもって頂点推移的である。

2部クネーザーグラフは、KGn,k2部二重被覆英語版として構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている (Simpson 1991)。2部クネーザーグラフ H5,2デザルググラフ英語版であり、2部クネーザーグラフ Hn,1王冠グラフ英語版である。

参考文献[編集]