正则图

此条目没有列出任何参考或来源。 (2019年6月21日)
维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。

此条目可参照英语维基百科相应条目来扩充。
若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

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

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

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

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

性质

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

代数性质

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

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