サイクルグラフ

サイクルグラフ
サイクルグラフC 5
胴回り	ん
自己同型	2 n ( 2 )の
彩度数	nが奇数の場合は3、 そうでない場合は2
色指数	nが奇数の場合は3、 そうでない場合は2
スペクトラム	${\displaystyle \left\{2\cos \left({\frac {2k\pi }{n}}\right);k=1,\cdots ,n\right\}}$[1]
プロパティ	2正則 頂点推移 辺推移 単位距離 ハミルトン オイラー
表記	Cn​
グラフとパラメータの表

グラフ理論において、サイクルグラフまたは循環グラフは、単一のサイクル、つまり閉じたチェーンで接続されたいくつかの頂点（グラフが単純な場合は少なくとも3つ）で構成されるグラフです。 n個の頂点を持つサイクルグラフはC _nと呼ばれます。^[2] C _nの頂点の数は辺の数に等しく、すべての頂点の次数は2です。つまり、すべての頂点にはちょうど2つの辺が接続しています。

の場合、それは孤立したループです。 ${\displaystyle n=1}$

「サイクルグラフ」には多くの同義語がある。これらには単純サイクルグラフや巡回グラフなどがあるが、後者の用語はあまり使われない。なぜなら、単に非巡回ではないグラフも指すからである。グラフ理論家の間では、サイクル、多角形、n角形もよく使われる。nサイクルという用語は、他の状況で使用されることもある。^[3]

頂点の数が偶数である閉路は偶閉路と呼ばれ、頂点の数が奇数である閉路は奇閉路と呼ばれます。

サイクルグラフとは次のようになります。

• 2辺が色付け可能で、頂点の数が偶数の場合に限ります。
• 2-レギュラー
• 2 頂点彩色可能グラフとは、頂点の数が偶数の場合に限ります。より一般的には、グラフが二部グラフである場合に限り、グラフに奇数サイクルがありません ( Kőnig、1936)。
• 接続
• オイラー
• ハミルトニアン
• 単位距離グラフ

加えて：

• サイクルグラフは正多角形として描くことができるため、nサイクルの対称性は、 n辺の正多角形、つまり位数 2 nの二面体群の対称性と同じです。特に、任意の頂点を他の任意の頂点に、任意の辺を他の任意の辺に取る対称性が存在するため、nサイクルは対称グラフです。

プラトングラフと同様に、サイクルグラフは二面体の骨格を形成し、その双対は双極子グラフであり、細面体の骨格を形成します。

有向サイクル グラフは、すべてのエッジが同じ方向を向いているサイクル グラフの有向バージョンです。

有向グラフでは、各有向サイクルからの少なくとも 1 つのエッジ (またはアーク)を含むエッジの集合は、フィードバックアーク集合と呼ばれます。同様に、各有向サイクルからの少なくとも 1 つの頂点を含む頂点の集合は、フィードバック頂点集合と呼ばれます。

有向サイクルグラフは、均一な入次数 1 と均一な出次数 1 を持ちます。

有向サイクルグラフは、巡回群のケイリーグラフです(例: Trevisan を参照)。

ウィキメディア・コモンズには、サイクルグラフに関連するメディアがあります。

• 完全二部グラフ
• 完全なグラフ
• 循環グラフ
• サイクルグラフ（代数）
• ヌルグラフ
• パスグラフ

• ディーステル、ラインハルト(2017).グラフ理論(第 5 版). Springer . ISBN 978-3-662-53621-6。

• Weisstein、Eric W.「サイクルグラフ」。MathWorld。（2-正則サイクルグラフとサイクル図の群論的概念の両方についての議論）
• ルカ・トレヴィサン、キャラクターと拡張。