正則グラフ

正則グラフ（せいそくグラフ、）は、グラフ理論において、各頂点の隣接する頂点数が全て同じであるようなグラフである。すなわち、全ての頂点の次数が等しい。頂点の次数が "k" の正則グラフを 「"k"-正則グラフ」または「次数 "k" の正則グラフ」と呼ぶ。
次数2までの正則グラフの分類は容易である。0-正則グラフは連結されていない頂点で構成され、1-正則グラフは連結されていない辺で構成され、2-正則グラフは連結されていない閉路で構成される。
3-正則グラフは立方体グラフとも呼ばれる。
正則グラフのうち、隣接する2つの頂点に共通する隣接点が常に同じ "l" 個で、隣接しない2つの頂点に共通する隣接点が常に同じ "n" 個となっているものを強正則グラフという。正則だが強正則でない最小のグラフは、6頂点の閉路グラフかつ循環グラフである。
完全グラフ formula_1 は任意の formula_2 について強正則である。
クリスピン・ナッシュ＝ウィリアムズの定理によれば、2"k"+1 個の頂点から成る "k"-正則グラフには必ずハミルトン路がある。
代数的属性.
あるグラフの隣接行列を "A" とする。そのグラフが正則であることは、"A" の固有ベクトルが formula_3 であることと同値である。その場合、その固有値はそのグラフの次数となる。他の固有値に対応した固有ベクトルは formula_4 と直交なので、そのような固有ベクトル formula_5 について formula_6 が成り立つ。
次数 "k" の正則グラフが連結していることと、固有値 "k" の重複度が1であることは同値である。
正則な連結グラフの判定基準も存在する。グラフが連結かつ正則であることと、formula_7 である行列 "J" がそのグラフの隣接代数（"A"の冪乗の1次結合）にあることは同値である。
グラフGは"k"-正則グラフで、直径D、隣接行列の固有値群は formula_8 とする。Gが2部グラフでないなら、次が成り立つ。
formula_9
ここで formula_10 である。
生成.
正則グラフを生成するソフトウェアとして GenReg がある。