主题
Search

电路秩

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

电路秩 mu 是从一个具有 m 条图边和 n 个节点的无向图中，必须移除的最少图边数，使得图中不再有图环。电路秩也给出了图的环基中的基本环的数量 (Harary 1994, pp. 37-40; White 2001, p. 56)。这个概念最初由古斯塔夫·基尔霍夫 (Gustav Kirchhoff) 提出 (Kirchhoff 1847; Veblen 1916, p. 9; Kotiuga 2010, p. 20)，并且已经被许多不同的名称和符号引用，如下表所示。

名称参考文献
电路秩
环秩Harary (1994, p. 39), White (2001, p. 56), Gross and Yellen (2006, pp. 192 and 661)
（第一）图贝蒂数White (2001), Gross and Yellen (2006, pp. 192)
圈数Listing (1862), Veblen (1916, pp. 9 and 18)
图的零度
符号参考文献
muVeblen (1916, pp. 9 and 18), Volkmann (1996), Babić et al. (2002)
gamma
betaGross and Yellen (2006, pp. 192 and 661), White (2001, p. 56)
mHarary (1994, p. 39)

对于一个具有 边数 m，顶点数 n 和 c 连通分量 的图，电路秩由下式给出：

mu=m-n+c.
(1)

电路秩给出了无向 图环 的总数的不等式 nu，如下所示：

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

(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996)。此外，

mu(G)=nu(G)
(3)

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

许多图的预计算值在 Wolfram 语言中实现为GraphData[g,"CircuitRank"].

另请参阅

巴拉班指数, 贝蒂数, 仙人掌图, 连通分量, 边数, 图环, 顶点数

使用 Wolfram|Alpha 探索

WolframAlpha

更多尝试

参考文献

Ahrens, W. "Über das Gleichungssystem einer Kirchhoffschen galvanischen Stromverzweigung." Math. Ann. 49, 311-324, 1897.Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, 1999.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.HararyHarary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.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.Kotiuga, P. R. A Celebration of the Mathematical Legacy of Raoul Bott. Providence, RI: Amer. Math. Soc., 2010.Listing, J. B. Census raumliche Komplexe. Göttingen, Germany: 1862.Mateti, P. and Deo, N. "On Algorithms for Enumerating All Circuits of a Graph." SIAM J. Comput. 5, 90-99, 1976.Veblen, O. Analysis Situs. New York: Amer. Math. Soc., 1916.Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.Wilson, R. J. Introduction to Graph Theory. Edinburgh: Oliver and Boyd, p. 46, 1971.

在 Wolfram|Alpha 中被引用

电路秩

请引用为

Weisstein, Eric W. "电路秩。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/CircuitRank.html

主题分类