閉路グラフ

閉路グラフ（Cycle Graph）

閉路グラフとは、グラフ理論において特定の構造を持つグラフの一種です。このグラフは、1つの閉路から成り、互いに接続された辺が一つの輪を形成しています。具体的には、n個の辺によって構成される閉路グラフは Cn （シーエヌ）と表記され、各辺の数と頂点の数は等しく、各頂点の次数は常に2となります。これにより、各頂点は他の2つの辺と接続されていることになります。

特に、nが1の場合には、孤立したループが形成されます。このような基本的な特性をもとに、閉路グラフにはいくつかの類義語が存在します。「単純閉路グラフ」や「環状グラフ」といった用語が一般的に使われることがありますが、環状グラフは広範な意味を持つため注意が必要です。また、頂点が偶数の閉路は「偶閉路」、奇数の場合は「奇閉路」と分類されます。

性質

閉路グラフが持つ性質は多岐にわたります。以下にその主要な性質を列挙します。

• - 連結グラフ：どの2つの頂点も接続されています。
• - 2-正則：全ての頂点の次数が2です。
• - オイラー路：各辺を一度だけ通る道が存在します。
• - ハミルトン路：各頂点を一度だけ訪れる道が存在します。
• - 偶数頂点の場合、2部グラフになる性質があります。この性質は、奇閉路でないことと同じ意味を持ちます。
• - 偶数頂点の場合に限り、2色で辺を彩色することが可能です。
• - 3色での頂点彩色や辺彩色が可能で、これは頂点の数に関係しません。
• - 単位距離グラフとしても知られています。

加えて、閉路グラフは正多角形として描くことができ、その対称性はn辺の正多角形と一致します。特に、どの2つの頂点間や辺間にも対称性が存在するため、閉路グラフは対称的な性質を持ったグラフといえるでしょう。

有向閉路グラフ

有向閉路グラフは、その名の通り、辺に向きがある閉路グラフです。このグラフでは、全ての辺が同じ方向に向いています。有向グラフにおいて、各有向閉路から少なくとも1つの辺を含む集合は「帰還枝集合」、同様に、各有向閉路から少なくとも1つの頂点を含む集合は「帰還頂点集合」と呼ばれます。このような特性により、有向閉路グラフでは各頂点の入次数と出次数が共に1になります。

また、有向閉路グラフは巡回群のケイリーグラフを表します。対照的に、閉路が存在しない有向グラフは「有向非巡回グラフ」として知られています。

まとめ

閉路グラフは、その独特の構造と多くの性質から、グラフ理論の中でも基本的かつ重要な概念の一つです。特に、その応用範囲の広さや他のグラフとの関連性により、様々な分野で用いられています。理解を深めることで、より複雑なグラフの理論や応用に進むための基盤となるでしょう。

もう一度検索