主題
Search

電路秩


電路秩 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頂點數 nc 連通分量 的圖,電路秩由下式給出:

 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_3K_4完全二分圖 K_(3,3),以及 K_4-e (Volkmann 1996)。

許多圖的預計算值在 Wolfram 語言中實現為GraphData[g,"CircuitRank"].


另請參閱

巴拉班指數, 貝蒂數, 仙人掌圖, 連通分量, 邊數, 圖環, 頂點數

使用 探索

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.

在 中被引用

電路秩

請引用為

Weisstein, Eric W. "電路秩。" 來自 —— 資源。 https://mathworld.tw/CircuitRank.html

主題分類