主題
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 的一組基本圈。


另請參閱

環秩, 圖的環

使用 探索

參考文獻

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. "基本圈。" 來自 —— 資源。 https://mathworld.tw/FundamentalCycle.html

主題分類