跳至內容

循環圖

維基百科,自由的百科全書
循環圖
長度為6的循環圖
頂點n
n
圍長n
自同構群2n (Dn)
色數n為奇數時為3,否則為2。
色指數n為奇數時為3,否則為2。
屬性2階正則圖
頂點傳遞圖
邊傳遞圖
單位距離圖
哈密頓圖
歐拉圖

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

術語

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

屬性

循環圖具有的屬性有:

此外:

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

有向循環圖

長度為8的有向循環圖

有向循環圖(directed cycle graph)是循環圖的有向版本,其中所有的邊都指向同一個方向。

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

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

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

參見

參考文獻

外部連結