循環圖
外觀
循環圖 | |
---|---|
![]() 長度為6的循環圖 | |
頂點 | n |
邊 | n |
圍長 | n |
自同構群 | 2n (Dn) |
色數 | n為奇數時為3,否則為2。 |
色指數 | n為奇數時為3,否則為2。 |
屬性 | 2階正則圖 頂點傳遞圖 邊傳遞圖 單位距離圖 哈密頓圖 歐拉圖 |
在圖論中,循環圖(cycle graph)或環形圖(circular graph)是由一個單環組成的圖,或者說是在一個閉合鏈中互相連接的若干頂點(至少3個)。有n個頂點的循環圖寫作Cn。Cn中的頂點個數等於邊的個數,每個頂點的度均為2;這意味着每個節點都是兩條邊的端點。
術語
[編輯]「循環圖」有許多同義詞。其中包括簡單循環圖(simple cycle graph)和周期圖(cyclic graph),儘管後者的使用頻率較低,因為它也可以指代不是有向無環圖的圖。在圖論中,環、多邊形或n邊形也經常被使用。術語n邊形有時用於其他領域。[1]頂點數為偶數的環稱為偶環;頂點數為奇數的循環稱為奇環。
屬性
[編輯]循環圖具有的屬性有:
此外:
有向循環圖
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/5/50/DC8.png)
有向循環圖(directed cycle graph)是循環圖的有向版本,其中所有的邊都指向同一個方向。
在有向圖中,每個有向循環中至少包含一條邊(或一條弧)的一組邊稱為反饋弧集。類似地,每個有向循環中至少包含一個頂點的一組頂點稱為反饋頂點集。
有向循環圖所有頂點的入度和出度均為1。
參見
[編輯]參考文獻
[編輯]- ^ Problem 11707. Amer. Math. Monthly. May 2013, 120 (5): 469–476. JSTOR 10.4169/amer.math.monthly.120.05.469. doi:10.4169/amer.math.monthly.120.05.469.
外部連結
[編輯]- 埃里克·韋斯坦因. Cycle Graph. MathWorld. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams)
- Luca Trevisan, Characters and Expansion (頁面存檔備份,存於互聯網檔案館).