正則グラフ

正則グラフ（せいそくグラフ、英: regular graph）は、グラフ理論において、各頂点の隣接する頂点数が全て同じであるようなグラフである。すなわち、全ての頂点の次数が等しい。頂点の次数が k の正則グラフを 「k-正則グラフ」または「次数 k の正則グラフ」と呼ぶ。

次数2までの正則グラフの分類は容易である。0-正則グラフは連結されていない頂点で構成され、1-正則グラフは連結されていない辺で構成され、2-正則グラフは連結されていない閉路で構成される。

3-正則グラフは立方体グラフとも呼ばれる。

正則グラフのうち、隣接する2つの頂点に共通する隣接点が常に同じ l 個で、隣接しない2つの頂点に共通する隣接点が常に同じ n 個となっているものを強正則グラフという。正則だが強正則でない最小のグラフは、6頂点の閉路グラフかつ循環グラフである。

完全グラフ $K_{m}$ は任意の $m$ について強正則である。

クリスピン・ナッシュ＝ウィリアムズの定理によれば、2k+1 個の頂点から成る k-正則グラフには必ずハミルトン路がある。

• 
  0-正則グラフ
• 
  1-正則グラフ
• 
  2-正則グラフ
• 
  3-正則グラフ

代数的属性

あるグラフの隣接行列を A とする。そのグラフが正則であることは、A の固有ベクトルが ${\textbf {j}}=(1,\dots ,1)$ であることと同値である。その場合、その固有値はそのグラフの次数となる。他の固有値に対応した固有ベクトルは ${\textbf {j}}$ と直交なので、そのような固有ベクトル $v=(v_{1},\dots ,v_{n})$ について $\sum _{i=1}^{n}v_{i}=0$ が成り立つ。

次数 k の正則グラフが連結していることと、固有値 k の重複度が1であることは同値である。

正則な連結グラフの判定基準も存在する。グラフが連結かつ正則であることと、$J_{ij}=1$ である行列 J がそのグラフの隣接代数（Aの冪乗の1次結合）にあることは同値である。

グラフGはk-正則グラフで、直径D、隣接行列の固有値群は $k=\lambda _{0}>\lambda _{1}\geq \dots \geq \lambda _{n-1}$ とする。Gが2部グラフでないなら、次が成り立つ。

$D\leq {\frac {\log {(n-1)}}{\log(k/\lambda )}}+1$

ここで $\lambda =\max _{i>0}\{\mid \lambda _{i}\mid \}$ である。

生成

正則グラフを生成するソフトウェアとして GenReg がある。

関連項目

• 強正則グラフ

外部リンク

• Weisstein, Eric W. "Regular Graph". mathworld.wolfram.com (英語).
• Weisstein, Eric W. "Strongly Regular Graph". mathworld.wolfram.com (英語).
• GenReg software and data by Markus Meringer.
• Nash-Williams, Crispin (1969), “Valency Sequences which force graphs to have Hamiltonian Circuits”, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo