主题
Search

循环图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
CirculantGraphs

循环图是一个具有 图 的 n 个 图顶点 的 图，其中第 i 个 图顶点 与第 (i+j) 个和第 (i-j) 个 图顶点 相邻，对于列表 l 中的每个 j。循环图 Ci_n(1,2,...,|_n/2_|) 给出了 完全图 K_n，图 Ci_n(1) 给出了 圈图 C_n。

在偏移列表 l 上具有 n 个顶点的循环图在 Wolfram 语言 中实现为CirculantGraph[n, l]。预计算属性可使用GraphData[{"Circulant", {n, l}}]。

除了 路径图 P_2 的退化情况外，连通循环图是 双连通 的，无桥 的，圈状 的，哈密顿 的，LCF 的，正则 的，可追踪 的和 顶点传递 的。

图 G 是循环图 当且仅当 G 的 自同构群 包含至少一个由长度为 |V(G)| 的最小循环组成的 置换。

CirculantGraphEnumeration

当 n=1, 2, ... 个节点时循环图的数量（将 空图 计为循环图）为 1, 2, 2, 4, 3, 8, 4, 12, ... (OEIS A049287)，其中前几个在上面说明。请注意，这些数字不能简单地通过枚举 {1,2,...,|_n/2_|} 的非空子集的数量来计数，因为例如 Ci_5(1)=Ci_5(2)=C_5。对于素数阶存在一个简单的公式，并且已知平方自由和素数平方阶的公式。

ConnectedCirculantGraphs

当 n=1, 2, ... 个节点时连通循环图的数量为 0, 1, 1, 2, 2, 5, 3, 8, ...，如上所示。

属于循环图的图类包括 Andrásfai 图，反棱柱图，鸡尾酒会图 K_(n×2)，完全图，完全二部图 K_(n,n)，冠图 2n-1，空图，KC 图 K_n square C_r，对于 (n,r)=1 （即 k 和 r 互质）和其中 square 表示 笛卡尔积，车图 L_(k,n) 对于 (k,n)=1，莫比乌斯梯子，素数阶的 Paley 图，棱柱图 Y_n，和 环面网格图 C_m square C_n 与 (m,n)=1 对应于 Ci_(mn)(m,n)）。特殊情况总结在下表中。

图符号
路径图 P_2Ci_2(1)
三角形图 C_3Ci_3(1)
正方形图 C_4Ci_4(1)
四面体图 K_4Ci_4(1,2)
圈图 C_5Ci_5(1)
五胞体图 K_5Ci_5(1,2)
圈图 C_6Ci_6(1)
八面体图 K_(2,2,2)Ci_6(1,2)
效用图 K_(3,3)Ci_6(1,3)
棱柱图 K_2 square C_3Ci_6(2,3)
完全图 K_6Ci_6(1,2,3)
圈图 C_7Ci_7(1)
完全图 K_7Ci_7(1,2,3)
圈图 C_8Ci_8(1)
4-反棱柱图Ci_8(1,2)
完全二部图 K_(4,4)Ci_8(1,3)
莫比乌斯梯子 M_4Ci_8(1,4)
16-胞 图Ci_8(1,2,3)
完全图 K_8Ci_8(1,2,3,4)
圈图 C_9Ci_9(1)
完全图 K_9Ci_9(1,2,3,4)
圈图 C_(10)Ci_(10)(1)
5-反棱柱图Ci_(10)(1,2)
冠图 K_2 square K_n^_Ci_(10)(1,3)
莫比乌斯梯子 M_5Ci_(10)(1,5)
棱柱图 K_2 square C_5Ci_(10)(2,5)
完全二部图 K_(5,5)Ci_(10)(1,3,5)
鸡尾酒会图 K_(5×2)Ci_(10)(1,2,3,4)
完全图 K_(10)Ci_(10)(1,2,3,4,5)

属于 单位距离 连通 循环图的族包括

1. 圈图 C_n=Ci_n(1)，

2. 棱柱图 C_n square P_2 和 P_2 的 笛卡尔积，产生 环面网格图 C_n square P_2 square P_2=C_4 square C_n=Ci_(n(n+1))(n,n+1)。

参见

16-胞, Andrásfai 图, 反棱柱图, 鸡尾酒会图, 完全图 完全二部图, 圈图, 空图, KC 图, 莫比乌斯梯子, 八面体图, Paley 图, 五胞体图, 棱柱图, 车图, 正方形图, 四面体图, 环面网格图, 三角形图, 效用图

在 Wolfram|Alpha 中探索

参考文献

Buckley, F. 和 Harary, F. 图中的距离。 Redwood City, CA: Addison-Wesley, 1990.Golin, M. J. 和 Leung, Y. C. "解开循环图：一种用于计数生成树和其他参数的组合方法。" 在 计算机科学中的图论概念。来自 2004 年 6 月 21-23 日在 Bad Honnef 举行的第 30 届国际研讨会的修订论文 (编辑 J. Hromkovič, M. Nagl, 和 B. Westfechtel). 柏林, 德国: Springer-Verlag, pp. 296-307, 2004.Lecture Notes in Comput. Sci., 3353, Springer, 柏林, 2004. Liskovets, V. A.; 和 Pöschel, R. "关于素数幂和平方自由阶循环图的枚举。" 预印本. MATH-AL-8-1996, TU-Dresden.Klin, M.; Liskovets, V.; 和 Pöschel, R. "具有素数平方顶点数的循环图的解析枚举。" Sém. Lothar. Combin. 36, Art. B36d, 1996.Muzychuk, M. "循环图的同构问题的解。" Proc. London Math. Soc. 88, 1-41, 2004.Skiena, S. 实现离散数学：组合学和图论与 Mathematica。 Reading, MA: Addison-Wesley, pp. 99 和 140, 1990.Zhou, A. 和 Zhang, X. D. "阶数为 n 且度数为 4 或 5 的循环图的枚举" [中文]。 电子科技大学学报 25, 272-276, 1996.

在 Wolfram|Alpha 上引用

循环图

请引用为

Weisstein, Eric W. "循环图。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/CirculantGraph.html

学科分类