正則グラフのソースを表示

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

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

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

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

[[完全グラフ]] <math>K_m</math> は任意の <math>m</math> について強正則である。

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

<gallery>
ファイル:0-regulární graf na 6 vrcholech.png|0-正則グラフ
File:1-regulární graf na 6 vrcholech.svg|1-正則グラフ
File:2-regulární graf na 6 vrcholech.svg|2-正則グラフ
File:3-regular graph2.svg|3-正則グラフ
</gallery>

== 代数的属性 ==
あるグラフの[[隣接行列]]を ''A'' とする。そのグラフが ''k''-正則であることは、ベクトル <math>\textbf{j}=(1, \dots ,1)</math> が[[固有値]] ''k'' に属する ''A'' の[[固有値|固有ベクトル]]であることと[[同値]]である<ref name="Cvetkovic">Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref>。他の[[固有値]]に対応した固有ベクトルは <math>\textbf{j}</math> と直交なので、そのような固有ベクトル <math>v=(v_1,\dots,v_n)</math> について <math>\sum_{i=1}^n v_i = 0</math> が成り立つ。

次数 ''k'' の正則グラフが連結していることと、固有値 ''k'' の重複度が1であることは同値である<ref name="Cvetkovic"/>。

正則な[[連結グラフ]]の判定基準も存在する。グラフが連結かつ正則であることと、<math>J_{ij}=1</math> である行列 ''J'' がそのグラフの[[隣接代数]]（''A''の冪乗の1次結合）にあることは同値である。{{要出典|date=2009年7月}}

グラフGは''k''-正則グラフで、直径D、隣接行列の固有値群は <math>k=\lambda_0 >\lambda_1\geq \dots\geq\lambda_{n-1}</math> とする。Gが[[2部グラフ]]でないなら、次が成り立つ。

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

ここで <math> \lambda=\max_{i>0}\{\mid \lambda_i \mid \}</math> である。{{要出典|date=2009年7月}}

== 生成 ==
正則グラフを生成するソフトウェアとして GenReg がある<ref>[http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html Regular Graphs] M. Meringer, J. Graph Theory, 1999, 30, 137.</ref>。

== 脚注・出典 ==
{{reflist}}

== 関連項目 ==
* [[強正則グラフ]]

== 外部リンク ==
* {{MathWorld|urlname=RegularGraph|title=Regular Graph}}
* {{MathWorld|urlname=StronglyRegularGraph|title=Strongly Regular Graph}}
* [http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html GenReg] software and data by Markus Meringer.
* {{Citation | last=Nash-Williams | first=Crispin |authorlink = | contribution=Valency Sequences which force graphs to have Hamiltonian Circuits | title=University of Waterloo Research Report | publisher=University of Waterloo | place=Waterloo, Ontario | year=1969 }}

{{Graph Theory-footer}}

{{DEFAULTSORT:せいそくくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]
[[Category:正則グラフ|*]]