グラフ

有限集合 $V$ と $k\in\mathbb{N}$ に対し, $\binom V k$ を $V$ の $k$ 元部分集合族, すなわち

\[\begin{align*} \binom V k = \left\{ U \subseteq V \colon \left| U \right| = k \right\} \end{align*}\]

とします.

有限集合$V$と$E\subseteq \binom V 2$の組 $G=(V,E)$ をグラフという.

• 集合$V$の元を頂点, $E$の元を辺という.
• グラフ$G$の頂点集合と辺集合をそれぞれ$V(G),E(G)$で表す.

例1

上の図で表されるグラフは

\[\begin{align*} &V = \left\{ 1,2,3,4 \right\},\\ &E = \left\{ \left\{ 1,2 \right\}, \left\{ 2,3 \right\},\left\{ 1,3 \right\},\left\{ 3,4 \right\} \right\} \end{align*}\]

で表されます.

例2

上の図で表されるグラフは

\[\begin{align*} &V = \left\{ 1,2,3,4,5,6 \right\},\\ &E = \left\{ \left\{ 1,2 \right\},\left\{ 2,3 \right\},\left\{ 1,3 \right\},\left\{ 4,5 \right\} \right\} \end{align*}\]

です.

有向グラフ

有向グラフとは各辺が向きを持つグラフです. 有限集合$V$と自然数$k\in \mathbb{N}$に対し, $V$の$k$個の要素からなる順序付きタプルの全体を$(V)_k$ とします. すなわち

\[\begin{align*} (V)_k = \left\{ (v_1,\dots,v_k) \in V^k \colon |\{v_1,\dots,v_k\}|=k\right\} \end{align*}\]

とします.

非空な有限集合$V$と$\vec E \subseteq (V)_2$ の組$\vec G=(V,\vec E)$を有向グラフという.

• 集合$V,E$をそれぞれ頂点集合, 有向辺集合と呼び, それらの要素をそれぞれ頂点, 有向辺 (または孤) と呼ぶ.
• グラフ$\vec G$の頂点集合と辺集合をそれぞれ$V(G),\vec E(G)$で表す.

グラフとの違いは単に辺の順序の有無だけです. 向きの有無を区別したい場合は有向グラフに対してグラフを特に無向グラフと呼ぶこともあります.

重み付きグラフ

各辺に長さまたは重みと呼ばれる値が割り当てられたグラフを重みグラフと呼びます.

グラフ$(V,E)$と関数$w\colon E \to \mathbb{R}$に対し, 三つ組$G=(V,E,w)$を重み付きグラフといい, 関数$w$を重みと呼ぶ.

重みは正であることを仮定することが多く, 負の値をとりうる場合は基本的にはそれを明示します. 文脈によっては重みのことを長さと呼ぶこともあります(最短経路問題など).