正則グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

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

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

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

代数的属性[編集]

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

次数 k の正則グラフが連結していることと、固有値 k の重複度が1であることは同値である[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 がある[2]

関連項目[編集]

脚注・出典[編集]

  1. ^ a b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
  2. ^ Regular Graphs M. Meringer, J. Graph Theory, 1999, 30, 137.

外部リンク[編集]