サイクルグラフ

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

グラフ理論において、サイクルグラフ（巡回グラフ）または円グラフとは、単一のサイクル、つまり、いくつかの頂点（グラフが単純であれば少なくとも3つ）が閉じた鎖状に接続されたグラフです。n個の頂点を持つサイクルグラフはC _nと呼ばれます。^[2] C _nの頂点数は辺の数と等しく、すべての頂点の次数は2です。つまり、すべての頂点にはちょうど2つの辺が接続されています。

サイクルグラフは孤立したループです。サイクルグラフは完全グラフと同じです。 ${\displaystyle C_{1}}$ ${\displaystyle C_{3}}$ ${\displaystyle K_{3}}$

用語

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

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

プロパティ

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

• 2辺が色付け可能で、頂点の数が偶数の場合に限ります。
• 2-レギュラー
• 2頂点彩色可能グラフとは、頂点数が偶数である場合に限ります。より一般的には、グラフが二部グラフである場合に限り、グラフに奇数閉路が存在しない（Kőnig , 1936）。
• 接続
• オイラー
• ハミルトニアン
• 単位距離グラフ

加えて：

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

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

有向循環グラフ

長さ8の有向閉路グラフ

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

有向グラフにおいて、各有向閉路から少なくとも1つの辺（または弧）を含む辺の集合は、フィードバック弧集合と呼ばれます。同様に、各有向閉路から少なくとも1つの頂点を含む頂点の集合は、フィードバック頂点集合と呼ばれます。

有向サイクルグラフには均一な入次数 1 と均一な出次数 1 があります。

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

参照

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

参考文献

1. いくつかの簡単なグラフスペクトル。win.tue.nl
2. ディーステル (2017) p.8, §1.3
3. 「問題11707」. Amer. Math. Monthly . 120 (5): 469– 476. 2013年5月. doi :10.4169/amer.math.monthly.120.05.469. JSTOR  10.4169/amer.math.monthly.120.05.469. S2CID  41161918.

出典

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

外部リンク

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