組合せとグラフの理論(塩田)第2回 (2) 有向グラフ
有向グラフ
もののつながり方に向きを考えたグラフを「有向グラフ」( digraph ) と呼びます。
有向グラフでは辺とは呼ばず「弧」( arc ) と呼び、
頂点 $u$ から出て $v$ へ至る弧を $a=uv$ と表します。
有向グラフ $D$ も、その頂点集合 $V=V(D)$ と弧集合 $A=A(D)$ のペアとして表します:
$D=(V,A)$
注意
無向グラフでは $uv$ と $vu$ は同じ辺を表しますが、
有向グラフでは向きが逆の異なる弧を表します。
Ex.2 頂点集合と弧集合が $V=\{\,1,2,3\,\}$, $A=\{\,12,23,32\,\}$ である有向グラフを描け。
解を折りたたむ
- $V=\{\,1,2,3\,\}$ なので、まず頂点 $1$, $2$, $3$ をプロットします。
- $A$ の要素 $12$, $23$, $32$ に従って、頂点 $1$ から $2$ へ至る弧、
$2$ から $3$ へ至る弧、$3$ から $2$ へ至る弧をそれぞれ描きます。