网站地图
正则图

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

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

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

在图论中,正则图中每个顶点具有相同数量的邻点; 即每个顶点具有相同的度或价态。正则的有向图也必须满足更多的条件,即每个顶点的内外自由度都要彼此相等。具有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不是二分的话


相关文章推荐:
| 价态 | 有向图 | | 价态 | 有向图 | 哈密尔顿 |
相关词汇词典