通常のグラフ

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

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

3 次正則グラフは、立方体グラフとして知られています。

強正則グラフとは、隣接する頂点のペアごとに、共通する隣接頂点の数が同じl個、隣接しない頂点のペアごとに、共通する隣接頂点の数が同じn個である正則グラフです。正則だが強正則ではない最小のグラフは、 6 頂点の サイクル グラフと巡回グラフです。

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

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

順序の -正則グラフが存在するための必要十分条件は、であり、が偶数であることです。 ${\displaystyle k}$ ${\displaystyle n}$${\displaystyle n\geq k+1}$${\displaystyle nk}$

証明:完全グラフでは、異なる頂点のすべてのペアが一意の辺で互いに接続されています。したがって、辺は完全グラフで最大になり、辺の数は で、次数は です。したがって、これは特定の に対する最小値です。また、任意の正則グラフに順序がある場合は辺の数が であるため、 は偶数でなければならないことにも注意してください。このような場合、巡回グラフの適切なパラメータを考慮することで、正則グラフを簡単に構築できます。 ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}}}$${\displaystyle n-1}$${\displaystyle k=n-1,n=k+1}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle {\dfrac {nk}{2}}}$${\displaystyle nk}$

ハンドシェイクの補題から、kが奇数であるk正則グラフには偶数個の頂点があります。

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

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

次数kの正則グラフは、固有値kの重複度が1である場合にのみ連結である。「場合にのみ」の方向は、ペロン・フロベニウスの定理の結果である。^[2]

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

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

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$^[4]

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

• ランダム正規グラフ
• 強正則グラフ
• ムーアグラフ
• ケージグラフ
• 非常に不規則なグラフ

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