閉路グラフのソースを表示

[[画像:Undirected 6 cycle.svg|thumb|right|160px|長さ6の閉路グラフ]]
'''閉路グラフ'''（へいろグラフ、{{lang-en-short|cycle graph}}）は、[[グラフ理論]]において1つの[[閉路]]から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪・環を形成しているグラフである。''n''個の辺による閉路グラフを ''C<sub>n</sub>'' と表記する。''C<sub>n</sub>'' においては、辺と頂点の数は等しく、各頂点の[[次数 (グラフ理論)|次数]]は2である。つまり、各頂点は2つの辺と接合している。

<math>n = 1</math> の場合は、孤立した[[グラフ理論|ループ]]となる。

== 用語について ==
「閉路グラフ」にはいくつか[[類義語]]がある。'''単純閉路グラフ''' (simple cycle graph) や'''環状グラフ''' (cyclic graph) といった用語があるが、後者は単に非環状でないグラフ全般（閉路を'''含む'''グラフ）を指すこともあるため、あまり使われない。'''多角形'''、'''''n''角形'''という呼び方をする場合もある。頂点が偶数個の閉路を'''偶閉路''' (even cycle)、頂点が奇数個の閉路を'''奇閉路''' (odd cycle) と呼ぶ。

== 性質 ==
閉路グラフには、以下の性質がある。
* [[連結グラフ]]である。
* [[正則グラフ|2-正則]]である。
* [[オイラー路]]である。
* [[ハミルトン路]]である。
* 頂点が偶数個の場合のみ[[2部グラフ]]である。より一般化すれば、2部グラフであることと奇閉路でないことは[[同値]]である。（Kőnig、1936）
* 頂点が偶数個の場合のみ[[グラフ彩色|2色の辺彩色]]が可能である。
* 頂点の個数に関係なく3色で頂点彩色または辺彩色が可能である。
* [[単位距離グラフ]]である。

さらに
* 閉路グラフは[[正多角形]]として描画できるため、''n''-閉路の対称性は、オーダー 2''n'' の[[二面体群]]である ''n'' 辺の正多角形の対称性と同じである。特に、任意の2つの頂点間にも任意の2つの辺間にも対称性があるため、''n''-閉路は[[対称グラフ]]である。

== 有向閉路グラフ ==
[[画像:DC8.png|frame|right|長さ8の有向閉路グラフ]]
'''有向閉路グラフ''' ({{lang-en-short|directed cycle graph}}) は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。

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

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

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

閉路のない有向グラフは[[有向非巡回グラフ]] ({{lang-en-short|directed acyclic graph}}) という

== 関連項目 ==
* [[完全2部グラフ]]
* [[完全グラフ]]
* [[空グラフ]]

== 外部リンク ==
{{commonscat|Cycle graphs}}
* Eric W. Weisstein, [http://mathworld.wolfram.com/CycleGraph.html Cycle Graph] at [[MathWorld]]（[[巡回グラフ]]のことも同じ項目で扱っている）
* Luca Trevisan, [https://in-theory.blogspot.com/2006/12/characters-and-expansion.html Characters and Expansion].

{{DEFAULTSORT:へいろくらふ}}

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