12.7 単純グラフにおける歩道

12.7.1 歩道・路・閉路

単純グラフの歩道と路は有向グラフのものと同様に定義されるので、有向グラフにおける定義の有向辺を無向辺に入れ替えれば定義できる。例えば、単純グラフの歩道は有向グラフの歩道 (定義 10.2.1) と本質的に何も変わらない:

定義 12.7.1

単純グラフの歩道 (walk) とは、次の条件を満たす列を言う:

頂点で始まる。
頂点で終わる。
頂点と辺が交互に並ぶ。
任意の辺 \(\langle u\>\text{---}\>v \rangle\) について、その辺の直前または直後のいずれかに頂点 \(u\) があり、もう一方に頂点 \(v\) がある。

言い換えれば、単純グラフ \(G\) の歩道 \(\mathbf{v}\) は次の形をしている:

\[ \mathbf{v} ::= (v_{0},\ \langle v_{0}\>\text{---}\>v_{1} \rangle,\ v_{1},\ \langle v_{1}\>\text{---}\> v_{2} \rangle,\ v_{2},\ \ldots,\ \langle v_{k-1}\>\text{---}\> v_{k} \rangle,\ v_{k}) \]

そして、全ての \(i \in [0..k)\) で \(\langle v_{i}\>\text{---}\>v_{i+1} \rangle \in E(G)\) が成り立つ。このとき:

\(\textbf{v}\) を「\(v_{0}\) から \(v_{k}\) への歩道」と呼ぶ。
\(v_{0}\) を歩道 \(\mathbf{v}\) の始点 (start) と呼ぶ。
\(v_{k}\) を歩道 \(\mathbf{v}\) の終点 (end) と呼ぶ。
\(k\) を歩道 \(\mathbf{v}\) の長さ (length) と呼ぶ。

特殊な歩道を次のように定義する:

\(v_{0}\), \(\ldots\), \(v_{k}\) が相異なる (\(i \neq j\) が \(v_{i} \neq v_{j}\) を含意する) 歩道を路 (path) と呼ぶ。
始点と終点が同じ (\(v_{0} = v_{k}\) が成り立つ) 歩道を閉歩道 (closed walk) と呼ぶ。単一の頂点だけからなる列は長さ \(0\) の閉歩道である。
始点と終点が同じで、その他の頂点が相異なる長さが \(3\) 以上の歩道を閉路 (cycle) と呼ぶ。

有向グラフと異なり、単純グラフでは長さ \(2\) の閉歩道を閉路とみなさない点に注意してほしい。同じ辺を往復するだけの閉歩道は退屈で重要性が低いためである。また、単純グラフは自己ループを持たないので長さ \(1\) の閉歩道は存在しない。

有向グラフと同様に、歩道の長さは歩道に含まれる辺の個数と定義される。つまり歩道に含まれる頂点の個数より \(1\) だけ少ない値が長さとなる。例えば、図 \(\text{12.14}\) のグラフにおいて \(7\) 個の頂点 \(abcdefg\) を連続してたどる歩道の長さは \(6\) である。また、このグラフは頂点列 \(bhecb\), \(cdec\), \(bcdehb\) で表される \(3\) 個の閉路を持つ。

bhecb, cdec, bcdehb で表される 3 個の閉路を持つグラフ — 図 12.14\(bhecb\), \(cdec\), \(bcdehb\) で表される \(3\) 個の閉路を持つグラフ

12.7.2 部分グラフとしての閉路

閉歩道は厳密な始点と終点を持たない。例えば図 \(\text{12.14}\) のグラフは \(b\) をスタートして \(bcdehb\) と頂点をたどる閉路を持つものの、本質的に同じ閉路は \(d\) をスタートして \(dehbcd\) と頂点をたどっても得られる。さらに、閉路は方向を持たない: 例えば \(dcbhed\) と逆方向の \(dehbcd\) は本質的に同じ閉路を表す。

こうした「同じ」閉路を厳密に議論するには、閉路グラフ \(C_{n}\) に同型な部分グラフ (subgraph) として閉路を捉える必要がある。

定義 12.7.2

グラフ \(G\) がグラフ \(H\) の部分グラフ (subgraph) とは、\(V(G) \subseteq V(H)\) と \(E(G) \subseteq E(H)\) が成り立つことを意味する。

例えば、辺を一つだけ持つグラフ \(G\) を次の等式で定義する:

\[ \begin{aligned} V(G) &= \left\{ g,\ h,\ i \right\} \\ E(G) &= \left\{ \langle h\>\text{---}\>i \rangle \right\} \\ \end{aligned} \]

このとき \(G\) は図 \(\text{12.1}\) のグラフ \(H\) の部分グラフである。一方で、\(H\) が持たない辺 \(\langle g\>\text{---}\>h \rangle\) を持つ任意のグラフは \(H\) の部分グラフでない。また、\(n\) 頂点の空グラフは (同じ頂点集合からなる) 線グラフ \(L_{n}\) の部分グラフ、\(L_{n}\) は閉路グラフ \(C_{n}\) の部分グラフ、\(C_{n}\) は完全グラフ \(K_{n}\) の部分グラフである。

次の定義を使うと、閉路が始点と終点を持たず、さらに向きも持たない事実を捉えられる:

定義 12.7.3

\(n \geq 3\) を整数とする。頂点集合が \([0..n)\) で辺集合が

\[ \left\{ \langle 0\>\text{---}\> 1 \rangle,\ \langle 1\>\text{---}\> 2 \rangle,\ \ldots,\ \langle (n-2)\>\text{---}\> (n-1) \rangle,\ \langle (n-1)\>\text{---}\> 0 \rangle \right\} \]

のグラフを \(C_{n}\) と定義する。グラフ \(G\) に対して、ある整数 \(n \geq 3\) で \(C_{n}\) と同型な \(G\) の部分グラフを \(G\) の閉路 (cycle) と呼ぶ。