正規グラフ

グラフ理論において、正則グラフとは、各頂点の近傍数が等しいグラフ、すなわちすべての頂点の次数または価数が等しいグラフのことである。正則有向グラフは、各内部頂点の入次数と出次数が互いに等しいという、より強い条件も満たす必要がある。 ^[1]次数 $k$ の頂点を持つ正則グラフは、 $k$ 正則グラフまたは次数 $k$ の正則グラフと呼ばれる。

特殊なケース

次数が最大 2 の正規グラフは簡単に分類できます。0正規グラフは切断された頂点で構成され、1 正規グラフは切断されたエッジで構成され、2 正規グラフはサイクルと無限チェーンの分離した結合で構成されます。

低次多項式の用語と同様に、3次正則グラフまたは4次正則グラフは、それぞれ3次グラフまたは4次グラフと呼ばれることが多い。同様に、 k次正則グラフを5次、6次、7次、8次などと表記することもできる。 $k=5,6,7,8,\ldots$

強正則グラフとは、隣接する頂点のペアが $l$ 個の頂点を共有し、隣接しない頂点のペアが $n$ 個の頂点を共有している正則グラフです。正則でありながら強正則ではない最小のグラフは、6頂点のサイクルグラフと巡回グラフです。

完全グラフ $K m$ $は任意のm$ に対して強正則です。

0-正規グラフ
1-正規グラフ
2-正規グラフ
3-正規グラフ

プロパティ

次数和公式によれば、 $n$ 頂点を持つ $k$ 正則グラフには辺が存在する。特に、位数 $n$ と次数 $k$ の少なくとも一方は偶数でなければならない。 ${\frac {nk}{2}}$

ナッシュ=ウィリアムズの定理によれば、 $2$ $k$ $+ 1$ 頂点上のすべての $k$ 正則グラフにはハミルトン閉路があります。

グラフの隣接行列をAとする。グラフが正則であるためには、Aの固有ベクトルが成り立つ必要がある。^[2] その固有値はグラフの定数次数となる。他の固有値に対応する固有ベクトルはAと直交するため、そのような固有ベクトルに対しては、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であることだ。「ただし」という方向は、ペロン＝フロベニウスの定理から導かれる。^[2]

正則かつ連結なグラフにも基準がある。グラフが連結かつ正則であるためには、1の行列 Jがグラフの隣接代数に含まれる（つまりAのべき乗の線形結合である）必要がある。^[3] $J_{ij}=1$

Gを直径D、隣接行列の固有値を持つk正則グラフとする。Gが二部グラフでない場合、 $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$

D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.

^[4]

存在

$自然数n$ と $k が$ 不等式を満たし、それが偶数である場合に限り、順序の -正則グラフが存在します。 $k$ $n$ $n\geq k+1$ $nk$

証明: $n$ 個の頂点を持つグラフが $k$ 正則である場合、任意の頂点vの次数 $kは、$ vとは異なる頂点の数を超えることはできず、実際には $n$ と $k$ の少なくとも 1 つは偶数でなければならないため、それらの積も偶数になります。 $n-1$

逆に、 $n$ と $k が$ 不等式と偶奇条件の両方を満たす2つの自然数である場合、確かに $n$ 位の $k$ 正則循環グラフが存在します（ただし、は、インデックスが an だけ異なる頂点が隣接するような最小の「ジャンプ」を表します）。さらに $k が$ 偶数の場合、となり、の選択肢があります。そうでない場合、 $k$ が奇数であるため、 $n は$ 偶数でなければならず、とすると、となり、「ジャンプ」はとして選択できます。 $C_{n}^{s_{1},\ldots ,s_{r}}$ $s_{i}$ $s_{i}$ $k=2r$ $(s_{1},\ldots,s_{r})=(1,2,\ldots,r)$ $n=2m$ $k=2r-1$ $(s_{1},\ldots,s_{r})=(1,2,\ldots,r-1,m)$

ならば、この循環グラフは完全です。 $n=k+1$

世代

与えられた次数と頂点数を持つすべての正則グラフを同型性まで生成する高速アルゴリズムが存在する。^[5]

参照

参考文献

^ 陳ワイカイ (1997).グラフ理論とその工学的応用. World Scientific. pp. 29. ISBN 978-981-02-1859-1。
^ ab Cvetković, DM; Doob, M.; Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
^ カーティン、ブライアン（2005）、「グラフ正則性条件の代数的特徴付け」、デザイン、コード、暗号化、34（2-3）：241-248、doi：10.1007/s10623-004-4857-4、MR 2128333 。
^ Quenell, G. (1994-06-01). 「k-正則グラフのスペクトル直径推定」 . Advances in Mathematics . 106 (1): 122– 148. doi :10.1006/aima.1994.1052. ISSN 0001-8708 . 2025年4月10日閲覧。[1]
^ Meringer, Markus (1999). 「正則グラフの高速生成とケージの構築」(PDF) . Journal of Graph Theory . 30 (2): 137– 146. doi :10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

外部リンク

ワイスタイン、エリック・W.「正則グラフ」。MathWorld。
ワイスタイン、エリック・W.「強正則グラフ」。MathWorld。
GenReg ソフトウェアとデータは Markus Meringer によるものです。
ナッシュ・ウィリアムズ、クリスピン（1969年）、グラフにハミルトン回路を強制する価数列、ウォータールー大学研究報告書、ウォータールー、オンタリオ州：ウォータールー大学