正則圖

提示：此條目的主題不是正圖形。

圖論中，正則圖（英語：regular graph）或正規圖是每個頂點都有相同數目的相鄰點的圖，即每個頂點都有相同的度。一個正則的有向圖也必須滿足對於每個頂點，其入度與出度相同。^[1]若每個頂點的度均為 ${\displaystyle k}$，稱為 ${\displaystyle k}$-正則圖（英語：k-regular graph）。

特殊例

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

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

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

強正則圖中，每對相鄰頂點都有 ${\displaystyle l}$ 個共同鄰居，每對非相鄰頂點也有 ${\displaystyle n}$ 個共同鄰居。最小的、正則而非強正則的圖是 6 個頂點的循環圖和環狀圖環狀圖（英語：Circulant graph）。

• 強 2-正則圖，稱為彼得森圖
• 強 5-正則圖，稱為克萊布殊圖（英語：Clebsch graph）

完全圖 ${\displaystyle K_{m}}$ 為對任意 ${\displaystyle m}$ 都是強正則圖。

• 
  0-正則圖
• 
  1-正則圖
• 
  2-正則圖
• 
  3-正則圖

性質

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

納許-威廉斯（英語：Crispin Nash-Williams）的定理指出，任何在 ${\displaystyle 2k+1}$ 個頂點上的 ${\displaystyle k}$-正則圖都包含一個漢米頓迴圈。

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

一個度數為 ${\displaystyle k}$ 的正則圖是連通的，當且僅當特徵值 ${\displaystyle k}$ 的重數為一。「僅當」的推導方向是 Perron–Frobenius 定理（英語：Perron–Frobenius theorem）的推論。

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

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

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

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

存在性

${\displaystyle n}$ 階 ${\displaystyle k}$-正則圖存在當且僅當自然數 ${\displaystyle n}$ 和 ${\displaystyle k}$ 滿足以下兩個條件：

1. ${\displaystyle n\geq k+1}$
2. ${\displaystyle nk}$ 是偶數

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

反之若 ${\displaystyle n}$ 和 ${\displaystyle k}$ 是滿足上述不等式 ${\displaystyle n\geq k+1}$ 和奇偶性條件（${\displaystyle nk}$ 為偶數）的兩個自然數，則確實存在一個 ${\displaystyle k}$-正則的環狀圖（英語：Circulant graph）${\textstyle C_{n}^{s_{1},\ldots ,s_{r}}}$，其階數為 ${\displaystyle n}$。這裏 ${\textstyle s_{i}}$ 表示最小的「跳躍（jump）」值，使得索引相差 ${\textstyle s_{i}}$ 的頂點是相鄰的。

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

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