コンテンツにスキップ

閉路

出典: フリー百科事典『ウィキペディア(Wikipedia)』
閉道から転送)

閉路(へいろ、: cycle)あるいは閉道(へいどう、: closed path)とは、グラフ理論の始点と終点が同じ道であることを指す。すなわち、出発点に戻るような辿り方であって頂点の重複がないグラフのことである。グラフ理論位相幾何学において用いられる。

閉路グラフ

[編集]

グラフの一種を言うこともある。n個の点vii=0, 1, ..., n -1)からなるグラフで、辺はちょうど、vivi+1i=0, 1, ..., n -1添字はn を法とする)を結んだものからなっているもの。Cnと表記。

閉路の検出

[編集]

深さ優先探索で親ノードへの戻り辺があれば、それは閉路である。トポロジカルソートでも検出できる。

関連項目

[編集]