循環圖

在圖論中，循環圖（cycle graph）或環形圖（circular graph）是由一個單環組成的圖，或者說是在一個閉合鏈中互相連接的若干頂點（至少3個）。有n個頂點的循環圖寫作C_n。C_n中的頂點個數等於邊的個數，每個頂點的度均為2；這意味著每個節點都是兩條邊的端點。

循環圖
長度為6的循環圖
頂點	n
邊	n
圍長	n
自同構群	2n (Dn)
色數	n為奇數時為3，否則為2。
色指數	n為奇數時為3，否則為2。
屬性	2階正則圖 頂點傳遞圖 邊傳遞圖 單位距離圖 哈密頓圖 歐拉圖
閱 論 編

術語

「循環圖」有許多同義詞。其中包括簡單循環圖（simple cycle graph）和周期圖（cyclic graph），儘管後者的使用頻率較低，因為它也可以指代不是有向無環圖的圖。在圖論中，環、多邊形或n邊形也經常被使用。術語n邊形有時用於其他領域。^[1]頂點數為偶數的環稱為偶環；頂點數為奇數的循環稱為奇環。

屬性

循環圖具有的屬性有:

• 2-邊可著色，若且唯若其頂點數為偶數時
• 2-正則圖
• 2-頂點可著色，若且唯若其頂點數為偶數時
• 連通圖
• 歐拉圖
• 哈密頓圖
• 單位距離圖

此外:

• 由於循環圖可以畫成正多邊形，因此n個周期的對稱性與邊數為n的正多邊形（2n階的二面體群）的對稱性相同。特別地，存在頂點或者邊互換的對稱性，因此n循環是對稱圖。

• 與柏拉圖的圖相似，循環圖形成了二面體的骨架。它們也是偶極圖，形成了多面形的骨架。

有向循環圖

長度為8的有向循環圖

有向循環圖（directed cycle graph）是循環圖的有向版本，其中所有的邊都指向同一個方向。

在有向圖中，每個有向循環中至少包含一條邊(或一條弧)的一組邊稱為反饋弧集。類似地，每個有向循環中至少包含一個頂點的一組頂點稱為反饋頂點集。

有向循環圖所有頂點的入度和出度均為1。

有向循環圖是循環群中的凱萊圖。

參見

• 完成兩分圖
• 完全圖
• 零圖
• 道路圖

參考文獻

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 （頁面存檔備份，存於網際網路檔案館）.