正则图

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

正则图是每个顶点都有相同数目的相邻点的图，即从每个顶点出发，所连接到的点的数目相同，这个数目用"度"来表示。若每个顶点的度均为$k$，称为$k$-正则图。

0-正则图是没有边的图。1-正则图由不相连的边组成。2-正则图由不相连的圈组成。3-正则图称为立方图或三次图。阶为$k$的$k-1$-正则图是$k$完全图。

在强正则图，每对相邻顶点都有相同数目 l 的共同邻居，每对非相邻顶点也有相同数目 m 节共同邻居。最小的正则而非强正则的图是6个顶点的环状图或圈。

• 
  0-正则图
• 
  1-正则图
• 
  2-正则图
• 
  3-正则图

性质

1. 对于每个图$G$及每个不小于$G$的最大度整数$r$，存在一个有$G$作子图的$r$-正则图。
2. 若有阶为$n$的$k$-正则图，k是偶数或n是偶数。

代数性质

设$A$为图$G$的邻接矩阵。$G$是正则图若且唯若${\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}$是A的特征向量。

图$G$是正则又连通的图若且唯若矩阵$J$（$J_{ij}=1$）在图的邻接代数内。