クネーザーグラフ

数学のグラフ理論におけるクネーザーグラフ（） とは、"n" 元集合の"k"元部分集合を各頂点に配し、互いに素な集合に対応する頂点を辺で結んだグラフのことを言う。1955年に初めて研究したマルティン・クネーザーの名にちなむ。
例.
"n" 個の頂点を持つ完全グラフはクネーザーグラフ である。
クネーザーグラフ は として知られる。奇グラフ はピーターセングラフと同型である。
関連するグラフ.
は、"n" 元集合の "k" 元部分集合が頂点となり、その -元部分集合が一致するとき、各頂点が隣接するようなグラフである。 に対して、ジョンソングラフはクネーザーグラフ の補となる。ジョンソングラフは、と密接に関係している。それらはいずれもの名にちなむ。
一般化クネーザーグラフ とは、クネーザーグラフと頂点集合は同じものであるが、二つの頂点が連結するための必要十分条件が、それらに対応する集合が "s" 以下の共通部分を持つこと、であるようなグラフのことである 。したがって、 である。
2部クネーザーグラフ （bipartite Kneser graph） は、"n" 個の元の集まりから抽出される "k" 個の元および 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 formula_1 でもって頂点推移的である。
2部クネーザーグラフは、 のとして構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている 。2部クネーザーグラフ はであり、2部クネーザーグラフ はである。