主题
Search

循环图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
CycleGraphs

在图论中，循环图 C_n, 有时也简称为 n-环 (Pemmaraju and Skiena 2003, p. 248), 是一个在 n 个节点上的图，包含一个穿过所有节点的单个环。 另一种循环图，此处称为群循环图，是一种图，它显示一个群的循环以及群循环之间的连通性。

循环图可以使用 Wolfram 语言生成，方法是CycleGraph[n]。 预计算属性可以使用GraphData[{"Cycle", n}]。 可以使用以下方法测试一个图是否为循环图PathGraphQ[g] &&Not[AcyclicGraphQ[g]]，其中需要第二次检查，因为 Wolfram 语言认为循环图也是路径图（这种约定充其量似乎是非标准的）。

特殊情况包括 C_3 ( 三角形图), C_4 ( 正方形图, 也同构于 网格图 G_(2,2)), C_6 (同构于 二部 Kneser 图 H(3,1)), 和 C_8 (同构于 2-Hadamard 图)。 2n-循环图同构于 Haar 图 H(2^(n-1)+1) 以及 Knödel 图 W_(2,2n)。

循环图（以及循环图的不相交并集）是2-正则的。 循环图也是唯一哈密顿图以及支配唯一图。

色数 C_n 由下式给出

chi(C_n)={3 for n odd; 2 for n even.
(1)

色多项式、独立多项式、匹配多项式和可靠性多项式是

pi(x)=(x-1)^n+(-1)^n(x-1)
(2)
I(x)=2(-x)^(n/2)T_n(1/(2sqrt(-x)))
(3)
mu(x)=2^(-n)[(x-sqrt(x^2-4))^n+(x+sqrt(x^2-4))^n]
(4)
C(p)=(1-p)^(n-1)[1+(n-1)p].
(5)

其中 T_n(x) 是第一类切比雪夫多项式。 这些对应于递推方程

pi_n(x)=(x-2)pi_(n-1)(x)+(x-1)pi_(n-2)(x)
(6)
I_n(x)=I_(n-1)(x)+xI_(n-2)(x)
(7)
mu_n(x)=xmu_(n-1)(x)-mu_(n-2)(x)
(8)
C_n(x)=-2(x-1)C_(n-1)(x)-(x-1)^2C_(n-2)(x).
(9)

循环图 C_n 的线图同构于 C_n 自身。

二部双图 C_n 当 n 为奇数时是 C_(2n) ，当 n 为偶数时是 2C_n 。

当 n>=4 时， C_n 的单纯形图是齿轮图 G_n。

另请参阅

二部 Kneser 图, 特征因子, 交叉棱柱图, 循环指标, 有环图, 图的环, Haar 图, Hadamard 图, 哈密顿环, 皮划艇桨图, KC 图, Knödel 图, 棒棒糖图, 平底锅图, 路径图, 正方形图, 蝌蚪图, 三角形图, 2-正则图, 路径 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

参考文献

Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, p. 13, 1999.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 144-147, 1990.

在 Wolfram|Alpha 上引用

循环图

请引用为

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

主题分类