循环图

图论中,循环图(cycle graph)环形图(circular graph)是由一个单环组成的,或者说是在一个闭合链中互相连接的若干顶点(至少3个)。有n个顶点的循环图写作CnCn中的顶点个数等于的个数,每个顶点的均为2;这意味着每个节点都是两条边的端点。

循环图
Undirected 6 cycle.svg
长度为6的循环图
顶点n
n
围长n
自同构群2n (Dn)
色数n为奇数时为3,否则为2。
色指数n为奇数时为3,否则为2。
属性2阶正则图
顶点传递图
边传递图
单位距离图
哈密顿图
欧拉图

术语

“循环图”有许多同义词。其中包括简单循环图(simple cycle graph)周期图(cyclic graph),尽管后者的使用频率较低,因为它也可以指代不是有向无环图的图。在图论中,多边形n边形也经常被使用。术语n边形有时用于其他领域。[1]顶点数为偶数的环称为偶环;顶点数为奇数的循环称为奇环

属性

循环图具有的属性有:

此外:

  • 由于循环图可以正多边形,因此n个周期的对称性与边数为n的正多边形(2n阶的二面体群)的对称性相同。特别地,存在顶点或者边互换的对称性,因此n循环是对称图
  • 柏拉图的图相似,循环图形成了二面体的骨架。它们也是偶极图,形成了多面形的骨架。

有向循环图

 
长度为8的有向循环图

有向循环图(directed cycle graph)是循环图的有向版本,其中所有的边都指向同一个方向。

有向图中,每个有向循环中至少包含一条边(或一条弧)的一组边称为反馈弧集。类似地,每个有向循环中至少包含一个顶点的一组顶点称为反馈顶点集

有向循环图所有顶点的入度和出度均为1。

有向循环图是循环群中的凯莱图

参见

参考文献

外部链接