路(Path)

グラフの鎖において辺が重複していないときその鎖を路(path)といいます。頂点は 重複していてもいいのです。このことは有向グラフでも無向グラフにおいても同じです。 また路の長さ(length) は鎖としての長さと同じです。

路の始点と路の終点も鎖のときと同じに考えます。

例2 V={A,B,C,D}, E={u,v,w,x},

s(u)=A, t(u)=B
s(v)=B, t(v)=C
s(w)=D, t(w)=C
s(x)=A, t(x)=D

即ち

において A,B,C,D u,v,w は長さ3の路です。これを ((A,B,C,D),(u,v,w))のように 記述することにします。すると((A,D,C),(x,w))も長さ2の路です。しかし((A,B,C,B),(u,v,v))は鎖ですが辺 v が重複していますので路ではありません。