閉路

提供: miniwiki
移動先:案内検索


ファイル:Directed cycle.svg
有向閉路の例。青い頂点を2度通るので単純閉路ではない。

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

単純閉路(たんじゅんへいろ、: simple cycle)とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。

閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。

n個の相異なる頂点vii=0, 1, ..., n -1)の列で、 vi, vi+1(添字はn を法とする)の間に辺が存在するもの。 viが相異なることを要求しない場合もあるが、そのときは閉道ではなく閉路という。

閉路グラフ

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

閉路の検出

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

関連項目