Chain(鎖)

有向グラフ(V,E,s(),t()),において 鎖(Chain)というのは次の条件(I)を満たす

頂点の列 v(1),v(2),v(3),....,v(n+1)
と辺の列 e(1),e(2),e(3),....,e(n)

をいいます(nは1以上の自然数)。v(1)を鎖の始点、v(n+1)を終点といいます。

(I) s(e(i))=v(i) and t(e(i))=v(i+1)

or s(e(i))=v(i+1) and t(e(i))=v(i) i=1,2,3,...,n

このときnをこの鎖の長さ(length)といいます。無向グラフ(V,E,T(.))の場合には (I)は

(I) {v(i),v(i+1)} = T(e(i)) i=1,2,3,...n.

で置き変わります。

例1 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の鎖です鎖は繋がっている頂点と辺の列であるといえるでしょう。