有向グラフの定義
有向グラフとは、頂点と向きのついた辺からなる「図形」 のことである。各辺がどの頂点からどの頂点に向かっているかという情報のみを与えることで定めることができる。点とそれを結ぶ辺の関係のみに注目し、辺の長さやまっすぐか曲がっているかなどの情報は一切与えない。
有向グラフ$G$とは、集合$V$と集合$E$及び写像$s:E\to V$と写像$t:E\to V$からなる$4$つ組$G=(V,E,s,t)$のこと。
$V$が頂点の集合、$E$が辺の集合であり、$s$と$t$は各辺に対して、その始点となる頂点及び終点となる頂点を対応させる写像であると解釈する。例えば$e\in E$に対して $s(e)=x, t(e)=y$となっていれば辺$e$は頂点$x$から頂点$y$に向かう辺であると解釈する。
$$
\begin{align*}
~& \hspace{20pt} e&~\\
\bullet &\hspace{15pt}\to &\bullet\\
x & ~ &y
\end{align*}
$$
$V=\{0\}, E=\emptyset$とする。
$s,t$はそれぞれ空集合を定義域とする唯一の写像$\emptyset \to \{0\}$とする。
これは頂点をただ一つもち頂点を持たない有向グラフ。
$$
\begin{align*}
\bullet\\
0
\end{align*}
$$
$V=\{0\}, E=\{a\}$とし、$s,t$をそれぞれ$s(a)=0,t(a)=0$で定まる写像$\{a\}\to\{0\}$とする。
これは頂点をただ一つもち、その頂点を始点と終点とするループをただ一つ持つ有向グラフ。
ループ一つのグラフ
$V=\{0,1\}, E=\{a\}$とする。
$s(a)=0, t(a)=1$により$s:\{a\}\to\{0,1\}, t:\{a\}\to\{0,1\}$を定める。
これは頂点を$0, 1$の$2$つ持ち、$0$から$1$に向かう辺をただ一つ持つ有向グラフ。
$$
\begin{align*}
~& \hspace{20pt} a&~\\
\bullet &\hspace{15pt}\to &\bullet\\
0 & ~ &1
\end{align*}
$$
もう少し頂点や辺の多い例については上の動画を参照ください。
