主题
Search

基本圈


如果 T 是一个连通、有限、无向图 G生成树,那么对应于 TG 的基本圈集是 G 的环 (u,v,...,u) 的集合,每个环由 G-T 的一条边 (u,v) 以及 T 中的唯一路径 (v,...,u) 组成 (Paton 1969)。

FundamentalCycles

恰好有

 nu=m-n+c

基本圈在一个图中,每个基本圈对应于一条不属于生成树的边。这里, nu环秩m边数n顶点数,并且 c 是连通分量的数量。上面用一个立方八面体图 说明了一组 13=24-12+1 个基本圈,图中还展示了图本身以及用于构建基的生成树

图的任何环都可以表示为图的基本圈集的模 2 和 (Gould 1959, Paton 1969)。

Wolfram 语言 函数FindFundamentalCycles[g] 可用于查找图 g 的一组基本圈。


另请参阅

环秩, 图的环

使用 Wolfram|Alpha 探索

参考文献

Gotlieb, C. C. and nd Corneil, D. G. "用于查找无向线性图的基本圈集的算法。" Comm. ACM 10, 780-783, 1967.Gross, J. T. and Yellen, J. 图论及其应用,第 2 版。 Boca Raton, FL: CRC Press, pp. 192-193, 2006.Gould, R. "图论在接触网络综合中的应用。" 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. 图论。 Reading, MA: Addison-Wesley, pp. 37-38, 1994.Paton, K. "用于查找图的基本圈的算法。" Comm. ACM 12, 514-518, 1969.Sch, P. "枚举无向图中的所有环。" 9 Sep 2018. https://www.codeproject.com/Articles/1158232/Enumerating-All-Cycles-in-an-Undirected-Graph.Welch, J. T. Jr. "无向线性图的循环结构的力学分析。" J. ACM 18, 2, 205-210, 1966.West, D. B. 图论导论,第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, p. 374, 2000.

请引用为

Weisstein, Eric W. "基本圈。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/FundamentalCycle.html

主题分类