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

クネーザーグラフ
クネーザーグラフ KG5,2
ピーターセングラフと同型)
命名者 マルティン・クネーザー
頂点
彩色数
特性 -正則
弧推移的
表記 KGn,k, K(n,k)
テンプレートを表示

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

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

性質

編集
  • クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず   個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。
である。
  に対し、固有値   が得られる。ここで、その重複度は、  に対しては   であり、  に対しては 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王冠グラフ英語版である。

参考文献

編集

外部リンク

編集
  • Weisstein, Eric W. "Kneser Graph". mathworld.wolfram.com (英語).
  • Weisstein, Eric W. "Odd Graph". mathworld.wolfram.com (英語).