正則圖

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

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

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

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

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

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

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

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

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

令  為圖的鄰接矩陣。則此圖是正則圖的充要條件是向量  是  的一個特徵向量。Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.這個特徵向量對應的特徵值即圖的常數度數。與其他特徵值對應的特徵向量  與  正交，因此對於這些特徵向量，我們有 。

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

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

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

假設 G 是一個直徑為 D 的 -正則圖，其鄰接矩陣的特徵值為 。如果 G 不是二分圖，則有：

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

  是偶數

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

反之若  和  是滿足上述不等式  和奇偶性條件（ 為偶數）的兩個自然數，則確實存在一個 -正則的，其階數為 。這裡  表示最小的「跳躍（jump）」值，使得索引相差  的頂點是相鄰的。

 若  是偶數，則 。此時，我們可以選擇跳躍值為 。
 若  是奇數，則  必須是偶數（因為  是偶數），假設 。此時 ，且跳躍值可以選擇為 。

如果 ，那麼這個環狀圖就是一個完全圖。

 參見 

 強正則圖

Category:離散數學
Category:圖論
Category:圖