正则图

如果一个图所有顶点的度是相同的，那么这个图被称为正则图（regular graph)，有奇数个结点。如果图G的每个顶点的度都是k，那么G被称为k-正则图。常见的正则图包括圈、完全图和完全二部图，其中二部图中的两个二部集合具有相同的基数^[1][2]。

正则图是指各顶点的度均相同的无向简单图。

在图论中，正则图中每个顶点具有相同数量的邻点； 即每个顶点具有相同的度或价态。正则的有向图也必须满足更多的条件，即每个顶点的内外自由度都要彼此相等。具有k个自由度的顶点的正则图被称为k度的k-正则图。 此外，奇数程度的正则图形将包含偶数个顶点。

最多2个等级的正则图很容易分类：0-正则图由断开的顶点组成，1-正则图由断开的边缘组成，2-正则图由断开的循环和无限链组成，3-正则图被称为立方图。

强规则图也是常规图，其中每个相邻的顶点对具有相同数量的相邻的相邻数目，并且每个不相邻的顶点对具有相同数量的n个相邻的相邻公共点。 常规但不太规则的最小图是循环图和6个顶点的循环图。

对于任何Km，完整的图m是强规则的。

纳什 - 威廉姆斯的一个定理说，2k + 1个顶点上的每个k-常规图都有一个哈密尔顿算子。

众所周知，k正则图存在的必要和充分条件是并且是偶数。在这种情况下，通过考虑循环图的适当参数，可以很容易地构建正则图。

令A成为正则图的相邻矩阵。然后，当且仅当是A的特征向量时，这个图才是正则的。其特征值将是图的不变自由度。对应于其他特征值的特征向量与j正交，因此对于这样的特征向量，我们有，

当且仅当特征值k具有多重性k时， “唯一的”方向是门阶 - 弗罗贝纽斯定理的结果。

还有一个正则和连接图的标准：当且仅当一个J的矩阵与时，图的相邻代数（意思是A的幂的线性组合）。