有向グラフの定義

5803

有向グラフとは、頂点と向きのついた辺からなる「図形」のことである。各辺がどの頂点からどの頂点に向かっているかという情報のみを与えることで定めることができる。点とそれを結ぶ辺の関係のみに注目し、辺の長さやまっすぐか曲がっているかなどの情報は一切与えない。

有向グラフ $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{aligned} e \\ ∙ & \to & ∙ \\ x & y \end{aligned}$

$V = {0}, E = \emptyset$ とする。
$s, t$ はそれぞれ空集合を定義域とする唯一の写像 $\emptyset \to {0}$ とする。
これは頂点をただ一つもち頂点を持たない有向グラフ。
$\begin{array}{r} ∙ \\ 0 \end{array}$

$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{aligned} a \\ ∙ & \to & ∙ \\ 0 & 1 \end{aligned}$

もう少し頂点や辺の多い例については上の動画を参照ください。

投稿日：2020年11月7日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

梅崎直也

27466

数学が好きです。

他の人のコメント

コメントはありません。

読み込み中

梅崎直也

有向グラフの定義