クネーザーグラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
クネーザーグラフ
Kneser graph KG(5,2).svg
クネーザーグラフ KG5,2
ピーターセングラフと同型)
命名者 マルティン・クネーザー
頂点 \textstyle\binom{n}{k}
\textstyle\binom{n}{k} \binom{n - k}{k} / 2
彩色数 \left\{\begin{array}{ll}n - 2 k + 2 & n \ge 2 k\\ 1 & \text{otherwise}\end{array}\right.
特性 \textstyle\binom{n - k}{k}-正則
弧推移的
表記 KGn,k, K(n,k)
テンプレートを表示

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

[編集]

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

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

性質[編集]

  • クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず \textstyle\binom{n-k}{k} 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフ英語版ではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。
である。
j=0,...,k に対し、固有値 \lambda_j=(-1)^j\binom{n-k-j}{k-j} が得られる。ここで、その重複度は、 j > 0 に対しては \binom{n}{j}-\binom{n}{j-1} であり、j = 0 に対しては 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部クネーザーグラフは次数 \textstyle\binom{n-k}{k} でもって頂点推移的である。

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

参考文献[編集]

外部リンク[編集]