正则图_各顶点的度均相同的无向简单图

正则图

各顶点的度均相同的无向简单图

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

简介

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

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

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

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

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

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

存在性

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

代数属性

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

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

还有一个正则和连接图的标准：当且仅当一个J的矩阵与Jij=1时，图的相邻代数（意思是A的幂的线性组合）。令G为具有直径D和相邻矩阵的特征值的k正则图

如果G不是二分的话

参考资料

最新修订时间：2024-06-13 15:30

条目作者

概述

简介

参考资料