有向グラフ

線図形の各辺が矢印であるようなものがあります。それに対応する概念として、有向グラフ(oriented graph)というものがあります。.

G=(V,E s(), t())

なる四つ組をいいます。

ここでV,Eは前節と同様の集合です。

s() は E から V への写像です。 辺の始点となる頂点を表します。

t() も E から V への写像です。 辺の終点となる頂点を表します。

辺 eE に対し、頂点 s(e) を e の 始点(source)といい, 頂点 t(e) を e の 終点(target)といいます。 有向グラフの図形としての意味は次の例でわかります。

例 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 が V の要素になっています。矢印付の辺が u,v,w,x でこれらはEの要素です。写像sは矢印の始点を表しtは終点を表します。