循环图

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

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

术语

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

属性

循环图具有的属性有:

• 2-边可着色，当且仅当其顶点数为偶数时
• 2-正则图
• 2-顶点可着色，当且仅当其顶点数为偶数时
• 连通图
• 欧拉图
• 哈密顿图
• 单位距离图

此外:

• 由于循环图可以画成正多边形，因此n个周期的对称性与边数为n的正多边形（2n阶的二面体群）的对称性相同。特别地，存在顶点或者边互换的对称性，因此n循环是对称图。

• 与柏拉图的图相似，循环图形成了二面体的骨架。它们也是偶极图，形成了多面形的骨架。

有向循环图

长度为8的有向循环图

有向循环图（directed cycle graph）是循环图的有向版本，其中所有的边都指向同一个方向。

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

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

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

参见

• 完成两分图
• 完全图
• 零图
• 道路图

参考文献

1. Problem 11707. Amer. Math. Monthly. May 2013, 120 (5): 469–476. JSTOR 10.4169/amer.math.monthly.120.05.469. doi:10.4169/amer.math.monthly.120.05.469.

外部链接

• 埃里克·韦斯坦因. Cycle Graph. MathWorld. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams)
• Luca Trevisan, Characters and Expansion （页面存档备份，存于互联网档案馆）.