道 (グラフ理論)
無向グラフだけでなく、有向グラフにも道はあり、頂点の列において常に前の頂点から次の頂点へ辺が向かっている。「有向道; directed path」、「有向閉道; directed cycle」といった呼称もよく使われる。
頂点が複数回出現しない道を単純道 (simple path) と呼び、始点/終点以外の頂点が複数回出現しない閉道を単純閉道 (simple cycle) と呼ぶ。最近では "simple"(単純)は最初から含意されていることが多く、閉道と言えば単純閉道を意味し、道といえば単純道を意味する。
ただし常にそういう意味で使われるとは限らない。書籍によっては(例えば Bondy and Murty 1976)、頂点が反復する道を歩道 (walk) と呼び、ここでいう単純道を道 (path) と呼んでいる。歩道(walk)から辺の反復を除いたものを小道(trail)という。