閉路グラフ
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Undirected_6_cycle.svg/160px-Undirected_6_cycle.svg.png)
閉路グラフ(へいろグラフ、英: cycle graph)は、グラフ理論において1つの閉路から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪・環を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は2である。つまり、各頂点は2つの辺と接合している。
の場合は、孤立したループとなる。
用語について
「閉路グラフ」にはいくつか類義語がある。単純閉路グラフ (simple cycle graph) や環状グラフ (cyclic graph) といった用語があるが、後者は単に非環状でないグラフ全般(閉路を含むグラフ)を指すこともあるため、あまり使われない。多角形、n角形という呼び方をする場合もある。頂点が偶数個の閉路を偶閉路 (even cycle)、頂点が奇数個の閉路を奇閉路 (odd cycle) と呼ぶ。
性質
閉路グラフには、以下の性質がある。
- 連結グラフである。
- 2-正則である。
- オイラー路である。
- ハミルトン路である。
- 頂点が偶数個の場合のみ2部グラフである。より一般化すれば、2部グラフであることと奇閉路でないことは同値である。(Kőnig、1936)
- 頂点が偶数個の場合のみ2色の辺彩色が可能である。
- 頂点の個数に関係なく3色で頂点彩色または辺彩色が可能である。
- 単位距離グラフである。
さらに
- 閉路グラフは正多角形として描画できるため、n-閉路の対称性は、オーダー 2n の二面体群である n 辺の正多角形の対称性と同じである。特に、任意の2つの頂点間にも任意の2つの辺間にも対称性があるため、n-閉路は対称グラフである。
有向閉路グラフ
![](http://upload.wikimedia.org/wikipedia/commons/5/50/DC8.png)
有向閉路グラフ (英: directed cycle graph) は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。
有向グラフにおいて、それぞれの有向閉路から少なくとも1つの辺(枝)を含んでいる枝集合を帰還枝集合 (feedback arc set) と呼ぶ。同様に、それぞれの有向閉路から少なくとも1つの頂点を含んでいる頂点集合を帰還頂点集合 (feedback vertex set) と呼ぶ。
有向閉路グラフの各頂点は入次数が1で、出次数が1である。
有向閉路グラフは、巡回群におけるケイリーグラフである(外部リンクの Trevisan 参照)。
閉路のない有向グラフは有向非巡回グラフ (英: directed acyclic graph) という
関連項目
外部リンク
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)