圖論中，正則圖（）或正規圖是每個頂點都有相同數目的相鄰點的圖，即每個頂點都有相同的度。一個正則的有向圖也必須滿足對於每個頂點，其入度與出度相同。若每個頂點的度均為 k，稱為 k-正則圖（）。

特殊例
度數至多為 2 的正則圖很容易分類：

• 0-正則圖是不相連的頂點組成
• 1-正則圖由不相連的邊組成
• 2-正則圖由不相連的環和無限鏈的互斥聯集組成

而 3-正則圖稱為立方圖或三次圖。4-正則圖則稱為四次圖（quartic graph）。同樣地，對於 k=5,6,7,8,\ldots 的 k-正則圖，可以分別稱為五次（quintic）、六次（sextic）、七次（septic）、八次（octic）圖等。

強正則圖中，每對相鄰頂點都有 l 個共同鄰居，每對非相鄰頂點也有 n 個共同鄰居。最小的、正則而非強正則的圖是 6 個頂點的循環圖和環狀圖。

• 強 2-正則圖，稱為彼得森圖
• 強 5-正則圖，稱為

完全圖 K_m 為對任意 m 都是強正則圖。

File: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-正則圖

性質
根據度求和公式，n 個頂點的 k-正則圖（稱為 n 階 k-正則圖）有 \frac{nk}{2} 條邊，n 或 k 至少其中一個是偶數。

的定理指出，任何在 2k+1 個頂點上的 k-正則圖都包含一個漢米頓迴圈。

令 A 為圖的鄰接矩陣。則此圖是正則圖的充要條件是向量 \textbf{j}=(1, \dots ,1)
是 A 的一個特徵向量。這個特徵向量對應的特徵值即圖的常數度數。與其他特徵值對應的特徵向量 v=(v_1,\dots,v_n) 與 \textbf{j} 正交，因此對於這些特徵向量，我們有 \sum\limits_{i=1}^n v_i = 0。

一個度數為 k 的正則圖是連通的，若且唯若特徵值 k 的重數為一。「唯若」的推導方向是 的推論。

還有一個判斷正則連通圖的準則：

一個圖是連通且正則的，當且僅當全一矩陣 J（其中 J_{ij}=1）屬於該圖的鄰接代數（ 即 J 可以表示為鄰接矩陣 A 各次冪的線性組合）。

假設 G 是一個直徑為 D 的 k-正則圖，其鄰接矩陣的特徵值為 k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}。如果 G 不是二分圖，則有：

D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1.

存在性
n 階 k-正則圖存在若且唯若自然數 n 和 k 滿足以下兩個條件：

n \geq k+1

nk 是偶數

證明：若一個具有 n 個頂點的圖是 k-正則的，則任何頂點 v 的度數 k 不可能超過除了 v 之外的其他 n-1 個頂點。因此，k \leq n-1，即 n \geq k+1。此外，根據握手引理，圖中所有頂點的度數之和（即 nk）必須是邊數的兩倍，所以 nk 必然是偶數。意味著 n 和 k 中至少有一個必須是偶數，進而它們的乘積 nk 也是偶數。

反之若 n 和 k 是滿足上述不等式 n \geq k+1 和奇偶性條件（nk 為偶數）的兩個自然數，則確實存在一個 k-正則的C_n^{s_1,\ldots,s_r}，其階數為 n。這裡 s_i 表示最小的「跳躍（jump）」值，使得索引相差 s_i 的頂點是相鄰的。

• 若 k 是偶數，則 k=2r。此時，我們可以選擇跳躍值為 (s_1,\ldots,s_r) = (1,2,\ldots,r)。
• 若 k 是奇數，則 n 必須是偶數（因為 nk 是偶數），假設 n=2m。此時 k=2r-1，且跳躍值可以選擇為 (s_1,\ldots,s_r) = (1,2,\ldots,r-1,m)。

如果 n=k+1，那麼這個環狀圖就是一個完全圖。

參見

• 強正則圖

参考资料