グラフの基礎的な概念

ここではグラフに関する基本的な用語の定義を紹介します. グラフ$G=(V,E)$を考えます.

次数

頂点$u\in V$に対し, $u$に接続している辺の本数を次数と呼び, $\deg_G(u)$で表す. グラフ$G$が文脈から明らかな場合は単に$\deg(u)$と表す.

特に, 全て頂点の次数が$d$に等しいグラフを$d$-正則グラフといいます. グラフの次数については握手補題と呼ばれる以下の有名な命題が成り立ちます.

任意のグラフ $G=(V,E)$に対して, 全ての頂点の次数の総和は辺の本数の二倍に等しい. すなわち

\[\begin{align*} \sum_{u\in V}\deg(u) = 2|E|. \end{align*}\]

証明

各頂点に対して, その頂点に接続する辺の本数(すなわち次数)を考える. このとき, 各辺$e=\left\{ u,v \right\}$はそれぞれ$u$と$v$における数え上げでカウントされるため, ちょうど二回カウントされる. よって, 次数の総和は辺の本数の二倍に等しい. $\square$

握手補題より, $n$頂点$d$-正則グラフは$nd$が偶数の時しか存在しえないことがわかります.

部分グラフ

グラフ$H=(U,F)$が$U\subseteq V$かつ$F\subseteq E$を満たすとき, $H$は$G$の部分グラフであるという. 特に, ある頂点部分集合$U\subseteq V$に対して$\left( U,\binom{U}{2}\cap E \right)$で与えられる部分グラフを誘導部分グラフと呼び, $G[U]$で表す.

路と閉路

頂点の列$(u_0,\dots,u_\ell) \in V^\ell$であって, 全ての$i=0,1,\dots,\ell-1$に対して $\left\{ u_i,u_{i+1} \right\}\in E$ を満たすものを路という.

• このときの$\ell$を長さといい, $u_0$を始点, $u_\ell$を終点と呼ぶ.
• 特に, $u_0 = u_\ell$を満たす路を閉路という.
• 路$(u_0,\dots,u_\ell)$の全ての頂点が相異なるとき, この路を特に単純路という.
• 同様に, $\ell\ge 3$ かつ $u_0,\dots,u_{\ell-1}$が全て相異なる($u_\ell$は含まれていないことに注意)ような閉路を単純閉路という.
• 始点が$s$, 終点が$t$であるような路を特に$st$-路と呼ぶ.

路を用いてグラフの頂点集合上に距離を以下のように定めることができます.

二頂点$s,t\in V$に対し, $st$-路の中での最小の長さを$st$間の距離と呼び, $\mathrm{dist}(s,t)$で表す.

• 距離に等しい長さを持つ$st$-路を最短$st$-路と呼ぶ.
• $st$-路が存在したいときは$\mathrm{dist}(s,t)=\infty$で表す.
• 全ての二頂点間に関して距離の最大値, すなわち$\max_{u,v\in V}\mathrm{dist}(u,v)$を直径という.

任意の二頂点$s,t\in V$に対し$st$-路が存在するようなグラフを連結グラフという.