グラフ

$V$ を有限集合とする。

無向グラフとは、対 $G=(V,E)$ であって $E \subseteq \{\, \{u,v\} \mid u,v \in V,\ u \ne v \,\}$ を満たすものをいう。$V$ の元を頂点、$E$ の元を辺という。

有向グラフとは、対 $G=(V,E)$ であって $E \subseteq V \times V$ を満たすものをいう。$(u,v)\in E$ を $u$ から $v$ への有向辺という。

無向グラフの頂点 $u$ の次数 $\deg(u)$ を、$u$ を含む辺の個数とする。有向グラフでは、$u$ を始点とする辺の個数を出次数 $\deg^{+}(u)$、$u$ を終点とする辺の個数を入次数 $\deg^{-}(u)$ とする。

さらに写像 $w : E \to \mathbb{R}$ が与えられているとき、$(G,w)$ を重み付きグラフといい、$w(e)$ を辺 $e$ の重みという。