主题
Search

图的圈

图图 G的圈，如果未指定第一个顶点，也称为环路，是边集 G的子集，它形成一个路径，使得路径的第一个节点对应于最后一个节点。 可以使用以下方法获得给定图g的边不相交圈的最大集合ExtractCycles[g] 在 Wolfram 语言 包中Combinatorica` .

精确使用图顶点一次的圈称为哈密顿圈。

不包含长度为 3 的圈的图称为无三角形图，不包含长度为 4 的圈的图称为无方形图。

不包含任何长度的圈的图称为无环图，而包含至少一个圈的图称为有环图。 恰好拥有一个（无向，简单）圈的图称为单圈图。 连通的无环图称为树，而可能不连通的无环图称为森林。

给定图中最短图圈的长度（如果有）称为围长，最长圈的长度称为图周长。

图的任何圈都可以表示为图的基本圈集的模 2 和（Gould 1959，Paton 1969）。

Björner 和 Wachs (1982) 以及 (Stanley 1999) 考虑了在循环的随机圆形嵌入中，将顶点置于其标准配置所需的最小交换次数。

无环图是二分图，并且有环图是二分图 当且仅当 其所有圈的长度均为偶数（Skiena 1990，第 213 页）。

具有邻接矩阵 A 的图中，长度为 k 的（无向）闭合路径的数量由 Tr(A^k) 给出，其中 Tr(A) 表示矩阵迹。 为了计算 k-圈的数量 c_k，必须减去所有不是圈的闭合 k-路径。 人们会认为，与匹配生成多项式、独立多项式等类似，应该定义一个圈多项式，其系数是长度为 k 的圈的数量。 虽然在文献中似乎没有定义这样的多项式（相反，“圈多项式”通常指的是对应于循环指标的置换群的多项式），但在这项工作中定义了它们。

k-圈的数量 c_k 与路径计数矩阵 P_k 相关，关系如下

c_k=1/(2k)Tr(P_(k-1)A),
(1)

其中 Tr 表示矩阵迹，A 是邻接矩阵 (Perepechko 和 Voropaev)。

对应于长度为 k 的闭合路径的图被称为 k-圈图，或简称为 “C_k-图”。 C_k-图的数量，对于 k=3, 4, ... 分别是 1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444, 7242, 21190, 67217, 217335, ... (OEIS A081809; FlowProblems)。

Harary 和 Manvel (1972) 给出了小 k 的以下闭合形式

6c_3=Tr(A^3)
(2)
8c_4=Tr(A^4)-2m-2sum_(i!=j)a_(ij)^((2))
(3)
=sum_(i)a_(ii)^((4))+sum_(i)a_(ii)^((2))-2sum_(i)sum_(j)a_(ij)^((2))
(4)
=Tr(A^4)+Tr(A^2)-2Tr(diag(A^2)^2)
(5)
=Tr(A^4)-2m-2sum_(i)d_i(d_i-1)
(6)
=Tr(A^4)+Tr(A^2)-2sum_(i)d_i^2
(7)
10c_5=Tr(A^5)-5Tr(A^3)-5sum_(i=1)(sum_(j)a_(ij)-2)a_(ii)^((3))
(8)

（c_4 变体来自 Perepechko 和 Voropaev），其中 m 是图的边数，a_(ij)^((k)) 表示 i,j 元素 A^k，diag(A) 是由 A 的对角线元素形成的矩阵，并且 d_i=a_(ii)^((2)) 是第 i 个顶点度。 Alon et al. (1997) 将这些结果扩展到 k=7，尽管只给出了直到 k=5 的显式公式。 c_6 和 c_7 的精确公式由下式给出

12c_6=sum_(i)a_(ii)^((6))-3sum_(n=1)^n(a_(ii)^((3)))^2+9sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)-6sum_(i)a_(ii)^((4))d_i+6sum_(i)a_(ii)^((4))-4sum_(i)a_(ii)^((3))+4sum_(i)d_i^3+3sum_(i)sum_(j)a_(ij)^((3))-12sum_(i)d_i^2+4sum_(i)d_i 14c_7=Tr(A^7)-7sum_(i)a_(ii)^((4))a_(ii)^((3))+7sum_(i)sum_(j)(a_(ij)^((2)))^3a_(ij)-7sum_(i)a_(ii)^((5))d_i+21sum_(i)sum_(j)a_(ij)^((3))a_(ij)^((2))a_(ij)+7Tr(A^5)-28sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)+7sum_(i)sum_(j)a_(ij)^((2))a_(ij)d_id_j+14sum_(i)a_(ii)^((3))d_i^2+7sum_(i)sum_(j)a_(ii)^((3))a_(ij)^((2))-77sum_(i)a_(ii)^((3))d_i+56Tr(A^3),
(9)

其中 d_i=a_(ii)^((2)) 是第 i 个顶点度（Perepechko 和 Voropaev；S. Perepechko，私人通信，2014 年 1 月 4 日）。

Khomenko 和 Golovko (1972) 给出了一个公式，可以给出任何长度的圈的数量，但其计算需要计算和执行涉及大小不超过 n-2 的所有子集的矩阵运算，这使得计算成本很高。 Khomenko 和 Golovko 公式的一个简化和改进版本由下式给出

c_k=1/(2k)sum_(i=2)^k(-1)^(k-i)(n-i; n-k)sum_(|S|=n-i)Tr(A_S^k)
(10)

对于 k=3, 4, ..., n，其中 A_S^k 是邻接矩阵 A 的子矩阵的第 k 次矩阵幂，其中删除了行和列的子集 S（Perepechko 和 Voropaev）。 因此，k=n 的情况给出了哈密顿圈的数量。

Giscard et al. (2016) 给出了图 G 中无向 k-圈数量的公式为

c_k=((-1)^k)/(2k)sum_(H≺_(conn)G)(|N(H)|; k-|H|)(-1)^(|H|)Tr(A_H^k),
(11)

其中总和是对 G 的连通导出子图 H 求和，N(H) 表示 H 在 G 中的邻居数（即 v 的顶点 G，它们不在 H 中，并且存在至少一条从 v 到 H 的顶点的边），Tr(A) 表示矩阵迹，而 A_H^k 是图 H 的邻接矩阵的第 k 次矩阵幂。

设 nu 表示图中无向圈的总数，mu 表示环秩。 那么

mu<=nu<=2^mu-1
(12)

（Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996）。 所有阶数为 n=1, 2, ... 的简单图的无向圈总数分别为 0, 0, 1, 13, 143, 1994, 39688, ... (OEIS A234601)。

mu(G)=nu(G)
(13)

当且仅当任何两个圈没有公共边时（Volkmann 1996）。 因此，在连通图中，等式对于（且仅对于）仙人掌图成立。 Mateti 和 Deo (1976) 证明，只有“本质上”四个图满足 nu=2^mu-1：完全图 K_3 和 K_4，完全二分图 K_(3,3)，以及 K_4-e (Volkmann 1996)。

无向圈的总数也满足

nu>=n(1/2delta-1)+1
(14)

和

nu>=1/2delta(delta-1),
(15)

其中 n 是顶点数，delta 是最小顶点度 (Volkmann 1996)。

下表给出了各种图类的无向图圈数。

图OEIS序列
Andrásfai 图A2346020, 1, 29, 1014, 72273, 9842527, ...
反棱柱图A077263X, X, 63, 179, 523, 1619, 5239, 17379, ...
主教图A234636X, 0, 3, 106, 17367, 24601058, 638520866656, ...
(n,n)-黑色主教图A234603X, X, X, 53, 12424, 12300529, ...
鸡尾酒会图 K_(n×2)A1679870, 1, 63, 2766, 194650, 21086055, 3257119761, ...
完全二分图 K_(n,n)A0709680, 1, 15, 204, 3940, 113865, 4662231, ...
完全三部图 K_(n,n,n)A2346161, 63, 6705, 1960804, 1271288295, 1541975757831, ...
完全图 K_nA0028071, 7, 37, 197, 1172, 8018, ...
2n-交叉棱柱图A23461728, 107, 380, 1345, 4878, 18219, ...
皇冠图A2346181, 28, 586, 16676, 674171, 36729512, ...
立方体连接圈图A000000X, X, 2664, ...
圈图 C_nA0000121, 1, 1, 1, 1, 1, 1, 1, ...
折叠立方体图A2346190, 0, 7, 204, 322248, ...
网格图 P_n square P_nA140517X, 1, 13, 213, 9349, 122236, 487150371, ...
网格图 P_n square P_n square P_nA234620X, 28, 3426491, ...
半立方体图A2346210, 0, 7, 2766, 4678134804, ...
河内图A0000001, 11, 1761, ...
超立方体图 Q_nA0854080, 1, 28, 14704, 51109385408, ...
(n,n)-国王图A234622X, 7, 348, 136597, 545217435, 21964731190911, ...
(n,n)-骑士图A234623X, 0, 1, 222, 128769, 959427728, ...
n-梯形图A0002170, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...
莫比乌斯梯形图 M_nA020873X, X, 15, 29, 53, 95, 171, 313, 585, ...
Mycielski 图A2346250, 0, 1, 337, 445228418, ...
奇图A3015580, 1, 57, 872137842, ...
置换星图A0000000, 0, 1, 5442, ...
棱柱图 Y_nA07726514, 28, 52, 94, 170, ...
(n,n)-皇后图A2346260, 7, 8215, 2080941496, 269529670654115055, ...
车图 K_n square K_nA2346240, 1, 312, 3228524, 6198979538330, ...
谢尔宾斯基垫片图A2346341, 11, 1033, ...
太阳图A234627X, X, 11, 44, 198, 1036, 6346, 45019, 364039, ...
太阳花图 C_n circledot K_1A000000X, X, 1, 1, 1, 1, 1, 1, 1, 1, ...
三角形图A2346290, 1, 63, 15703, 58520309, ...
网状图A07726514, 28, 52, 94, 170, 312, 584, 1114, ...
轮图 W_nA0020617, 13, 21, 31, 43, 57, ...
(n,n)-白色主教图A234630X, X, X, 53, 4943, 12300529, ...

下表总结了其中一些图类的闭合形式。

图公式
反棱柱图a_n=6a_(n-1)-11a_(n-2)+8a_(n-3)-3a_(n-4)+2a_(n-5)-a_(n-6)
完全二分图 K_(n,n)1/2sum_(k=2)^(n)k!(k-1)!(n; k)^2
完全图 K_n1/2sum_(k=3)^(n)(k-1)!(n; k)=1/4n[2_3F_1(1,1,1-n;2;-1)-n-1]
圈图 C_n1
梯形图(n; 2)
莫比乌斯梯形图1+2^n+n(n-1)
棱柱图 Y_n2^n+n(n-1)
太阳花图 C_n circledot K_11
网状图 f2^n+n(n-1)
轮图 W_n2(n-1)

参见

无环有向图, 无弦圈, 环路, 圈弦, 圈图, 圈多项式, 有环图, 欧拉圈, 欧拉图, 欧拉路径, 森林, 基本圈, 围长, 图周长, 图路径, 哈密顿圈, 哈密顿图, k-圈图, Markström 图, 无方形图, 迹, 无三角形图, 单圈图, 路径 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

WolframAlpha

更多尝试

参考文献

Ahrens, W. "Über das Gleichungssystem einer Kirchhoffschen galvanischen Stromverzweigung." Math. Ann. 49, 311-324, 1897.Alon, N.; Yuster, R.; and Zwick, U. "Finding and Counting Given Length Cycles." Algorithmica 17, 209-223, 1997.Björner, A. and Wachs, M. "Bruhat Order of Coxeter Groups and Shellability." Adv. Math. 43, 87-100, 1982.FlowProblem. "C_k-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. https://arxiv.org/pdf/1612.05531.pdf.Gould, R. "The Application of Graph Theory to the Synthesis of Contact Networks." Proc. International Symp. on the Theory of Switching, Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of Harvard University, Annals No. 29. Cambridge, MA: Harvard University Press, pp. 244-292, 1959.Harary, F. and Manvel, B. "On the Number of Cycles in a Graph." Mat. Časopis Sloven. Akad. Vied 21, 55-63, 1971.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Khomenko, N. P. and Golovko, L. D. "Identifying Certain Types of Parts of a Graph and Computing Their Number." Ukr. Math. J. 24, 313-321, 1972.Kirchhoff, G. "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Ann. d. Phys. Chem. 72, 497-508, 1847.König, D. Theorie der endlichen und unendlichen Graphen. Leipzig, Germany: Akademische Verlagsgesellschaft, 1936.Mateti, P. and Deo, N. "On Algorithms for Enumerating All Circuits of a Graph." SIAM J. Comput. 5, 90-99, 1976.Paton, K. "An Algorithm for Finding Fundamental Cycles of a Graph." Comm. ACM 12, 514-518, 1969.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Skiena, S. "Cycles in Graphs." §5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 188-202, 1990.Sloane, N. J. A. Sequences A000012/M0003, A002061/M2638, A002807/M4420, A077263, A077265, A081809, and A234601 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999.Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 5 and 20, 2000.

在 Wolfram|Alpha 上引用

图的圈

请引用为

Weisstein, Eric W. "图的圈." 来自 MathWorld--Wolfram Web 资源. https://mathworld.net.cn/GraphCycle.html

主题分类