主題
Search

迴圈圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
CycleGraphs

在圖論中，迴圈圖 C_n, 有時也簡稱為 n-環 (Pemmaraju and Skiena 2003, p. 248), 是一個在 n 個節點上的圖，包含一個穿過所有節點的單個環。 另一種迴圈圖，此處稱為群迴圈圖，是一種圖，它顯示一個群的迴圈以及群迴圈之間的連通性。

迴圈圖可以使用 Wolfram 語言生成，方法是CycleGraph[n]。 預計算屬性可以使用GraphData[{"Cycle", n}]。 可以使用以下方法測試一個圖是否為迴圈圖PathGraphQ[g] &&Not[AcyclicGraphQ[g]]，其中需要第二次檢查，因為 Wolfram 語言認為迴圈圖也是路徑圖（這種約定充其量似乎是非標準的）。

特殊情況包括 C_3 ( 三角形圖), C_4 ( 正方形圖, 也同構於 網格圖 G_(2,2)), C_6 (同構於 二部 Kneser 圖 H(3,1)), 和 C_8 (同構於 2-Hadamard 圖)。 2n-迴圈圖同構於 Haar 圖 H(2^(n-1)+1) 以及 Knödel 圖 W_(2,2n)。

迴圈圖（以及迴圈圖的不相交併集）是2-正則的。 迴圈圖也是唯一哈密頓圖以及支配唯一圖。

色數 C_n 由下式給出

chi(C_n)={3 for n odd; 2 for n even.
(1)

色多項式、獨立多項式、匹配多項式和可靠性多項式是

pi(x)=(x-1)^n+(-1)^n(x-1)
(2)
I(x)=2(-x)^(n/2)T_n(1/(2sqrt(-x)))
(3)
mu(x)=2^(-n)[(x-sqrt(x^2-4))^n+(x+sqrt(x^2-4))^n]
(4)
C(p)=(1-p)^(n-1)[1+(n-1)p].
(5)

其中 T_n(x) 是第一類切比雪夫多項式。 這些對應於遞推方程

pi_n(x)=(x-2)pi_(n-1)(x)+(x-1)pi_(n-2)(x)
(6)
I_n(x)=I_(n-1)(x)+xI_(n-2)(x)
(7)
mu_n(x)=xmu_(n-1)(x)-mu_(n-2)(x)
(8)
C_n(x)=-2(x-1)C_(n-1)(x)-(x-1)^2C_(n-2)(x).
(9)

迴圈圖 C_n 的線圖同構於 C_n 自身。

二部雙圖 C_n 當 n 為奇數時是 C_(2n) ，當 n 為偶數時是 2C_n 。

當 n>=4 時， C_n 的單純形圖是齒輪圖 G_n。

另請參閱

二部 Kneser 圖, 特徵因子, 交叉稜柱圖, 迴圈指標, 有環圖, 圖的環, Haar 圖, Hadamard 圖, 哈密頓環, 皮划艇槳圖, KC 圖, Knödel 圖, 棒棒糖圖, 平底鍋圖, 路徑圖, 正方形圖, 蝌蚪圖, 三角形圖, 2-正則圖, 路徑 在 課堂中探索此主題

使用 探索

參考文獻

Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, p. 13, 1999.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 144-147, 1990.

在 上引用

迴圈圖

請引用為

Weisstein, Eric W. "迴圈圖。" 來自 Web 資源。 https://mathworld.tw/CycleGraph.html

主題分類