閉路
表示
(閉道から転送)
![]() |
閉路(へいろ、英: cycle)あるいは閉道(へいどう、英: closed path)とは、グラフ理論の始点と終点が同じ道であることを指す。すなわち、出発点に戻るような辿り方であって頂点の重複がないグラフのことである。グラフ理論や位相幾何学において用いられる。
閉路グラフ
[編集]詳細は「閉路グラフ」を参照
グラフの一種を言うこともある。n個の点vi(i=0, 1, ..., n -1)からなるグラフで、辺はちょうど、vi とvi+1(i=0, 1, ..., n -1添字はn を法とする)を結んだものからなっているもの。Cnと表記。
閉路の検出
[編集]深さ優先探索で親ノードへの戻り辺があれば、それは閉路である。トポロジカルソートでも検出できる。