閉路グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/05 14:20 UTC 版)
閉路グラフ（へいろグラフ、英: cycle graph）は、グラフ理論において1つの閉路から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪・環を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は2である。つまり、各頂点は2つの辺と接合している。
有向閉路グラフ (英: directed cycle graph) は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。
有向グラフにおいて、それぞれの有向閉路から少なくとも1つの辺（枝）を含んでいる枝集合を帰還枝集合 (feedback arc set) と呼ぶ。同様に、それぞれの有向閉路から少なくとも1つの頂点を含んでいる頂点集合を帰還頂点集合 (feedback vertex set) と呼ぶ。
有向閉路グラフの各頂点は入次数が1で、出次数が1である。
有向閉路グラフは、巡回群におけるケイリーグラフである（外部リンクの Trevisan 参照）。
閉路のない有向グラフは有向非巡回グラフ (英: directed acyclic graph) という
関連項目
外部リンク
- Eric W. Weisstein, Cycle Graph at MathWorld（巡回グラフのことも同じ項目で扱っている）
- Luca Trevisan, Characters and Expansion.
閉路グラフと同じ種類の言葉
このページでは「ウィキペディア」から閉路グラフを検索した結果を表示しています。
Weblioに収録されているすべての辞書から閉路グラフを検索する場合は、下記のリンクをクリックしてください。
全ての辞書から閉路グラフ
を検索
Weblioに収録されているすべての辞書から閉路グラフを検索する場合は、下記のリンクをクリックしてください。
全ての辞書から閉路グラフ
を検索
- 閉路グラフのページへのリンク
