グラフ

有向グラフ

• $V,A$ を集合とし, $f: A \to V \times V$ を写像とする. トリプル $D:=(V,A,f)$ を有向グラフという.
  • $V$ の元を頂点, $A$ の元を孤という.
  • 写像 $f$ を明示せずに, ペア $D:=(V,A)$ を有向グラフということもある.
• $a \in A$ に対して, $f(a)=(u,v)$ であるとき, $u$ を $a$ の始点, $v$ を $a$ の終点という.
  • このとき, $a = \overrightarrow{uv}$ と書くこともある.
• 特別な辺の名前
  • 始点と終点が一致する孤は自己ループであるという.
  • $a,b \in A$ で $a \neq b, f(a) = f(b)$ であるとき, $a,b$ は多重辺であるという.
  • 自己ループも多重辺もないグラフを単純グラフという.

無向グラフ

• $V,E$ を集合とし, $g: E \to \mathcal{P}(V)$ を写像とする. 任意の $e \in E$ に対して, $g(e)$ の濃度が $1$ または $2$ であるとする. このとき, トリプル $G:=(V,E,g)$ を無向グラフという.
  • $V$ の元を頂点, $E$ の元を辺という.
  • 写像 $g$ を明示せずに, ペア $G:=(V,E)$ を有向グラフということもある.
• $e \in E$ に対して, $g(e)={u,v}$ であるとき, $u,v$ を $e$ の端点という.
  • このとき, $e = uv$ と書くこともある.
• 特別な辺の名前
  • 端点が唯一である辺は自己ループであるという.
  • $e,f \in A$ で $e \neq f, g(e) = g(f)$ であるとき, $e,f$ は多重辺であるという.
  • 自己ループも多重辺もないグラフを単純グラフという.