正则图

提示：此条目的主题不是正图形。

图论中，正则图（英语：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}$，那么这个环状图就是一个完全图。