閉路グラフ

閉路グラフ（へいろグラフ、）は、グラフ理論において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-閉路は対称グラフである。

 有向閉路グラフ 
有向閉路グラフ () は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。

有向グラフにおいて、それぞれの有向閉路から少なくとも1つの辺（枝）を含んでいる枝集合を帰還枝集合 (feedback arc set) と呼ぶ。同様に、それぞれの有向閉路から少なくとも1つの頂点を含んでいる頂点集合を帰還頂点集合 (feedback vertex set) と呼ぶ。

有向閉路グラフの各頂点は入次数が1で、出次数が1である。

有向閉路グラフは、巡回群におけるケイリーグラフである（外部リンクの Trevisan 参照）。

閉路のない有向グラフは有向非巡回グラフ () という

 関連項目 
 完全2部グラフ
 完全グラフ
 空グラフ

 外部リンク 

 Eric W. Weisstein, Cycle Graph at MathWorld（巡回グラフのことも同じ項目で扱っている）
 Luca Trevisan, Characters and Expansion.

Category:グラフ理論のグラフ
Category:数学に関する記事