10.2 歩道と路

有向グラフを点と矢印で図示すると、矢印をたどって頂点間を移動する道筋が自然に考えられる。例えば図 \(\text{10.5}\) の有向グラフでは、頂点 \(1\) をスタートしてから矢印をたどって \(2\), \(4\), \(12\), \(12\), \(12\) と移動できる (最後の \(12\) は何度でも繰り返せる)。こういった移動の道筋を歩道 (walk) と呼ぶ。また、同じ頂点を二度以上通らない歩道を路 (path) と呼ぶ。例えば \(1\), \(2\), \(4\), \(12\) とたどる道筋は路であるのに対して、この路の最後に \(12\) を付け足すと路でなくなる。

歩道の自然な表現は通り抜ける頂点の列を使うものである。例えば上述の歩道は次の列で表現される:

しかし、歩道は頂点と辺が交互に並ぶ列として表現するのが慣習となっている。つまり、この歩道は次の列として表現される:

この定義の冗長性は情報科学者を震え上がらせるかもしれない。しかし、この冗長性のおかげで歩道に頂点と辺が含まれる回数を簡単に議論できるようになる。形式的な定義を次に示す:

一つの頂点 \(v\) からなる列は長さ \(0\) の歩道であり、その始点と終点は \(v\) で等しい。この列は閉歩道であり、閉路でない: 閉路は正の長さを持つ必要がある。長さ \(1\) の閉路は、始点と終点が同じ辺を持つ有向グラフにのみ存在できる。例えば図 \(\text{10.1}\) の有向グラフに長さ \(1\) の閉路は存在せず、図 \(\text{10.5}\) の整除性グラフでは任意の頂点だけからなる列が長さ \(1\) の閉路となる。長さ \(1\) の閉路は自己ループ (self-loop) と呼ばれることがある。

歩道の正式な定義は頂点と辺が交互に並ぶ列であるものの、含まれる頂点の列または辺の列から歩道は完全に決定される。そのため、本書では歩道を表記するとき便利な方を使うことにする。さらに、列の表記に含まれる括弧とコンマも場合によっては省略する。例えば、図 \(\text{10.1}\) のグラフにおいて:

• \((a, b, d)\) は長さ \(2\) の路 (を頂点の列としての表現したもの) である。この路は \(abd\) とも表記される。

• \((\langle a \to b \rangle, \langle b \to d \rangle)\) は同じ長さ \(2\) の路 (を辺の列としての表現したもの) である。この路は\(\langle a \to b \rangle \langle b \to d \rangle\) とも表記される。

• \(abcbd\) は長さ \(4\) の歩道である。

• \(dcbcbd\) は長さ \(5\) の閉歩道である。

• \(bdcb\) は長さ \(3\) の閉路である。

• \(\langle b \to c \rangle, \langle c \to b \rangle\) は長さ \(2\) の閉路である。

• \(\langle c \to b \rangle \langle b \leftarrow a \rangle \langle a \to d \rangle\) は歩道でない。歩道は辺を順方向にたどる必要がある。

歩道に沿って移動している途中に何らかの頂点で立ち止まり、少し休んでから歩道に沿った移動を再開するとき、歩道は二つの部分に分かれる。例えば、整除性グラフの歩道 \(\text{(10.1)}\) で辺を二つ進んでから止まると、歩道は \(1\) から \(4\) に進む

の部分と、\(4\) から \(12\) に進む次の部分に分割される:

このとき、歩道 \(\text{(10.1)}\) は歩道 \(\text{(10.2)}\) と歩道 \(\text{(10.3)}\) の結合と言う。一般に、歩道 \(\mathbf{f}\) の終点が \(v\) で歩道 \(\mathbf{r}\) の始点が \(v\) のとき、\(\mathbf{f}\) の始点から始まって \(\mathbf{f}\) と \(\mathbf{r}\) に含まれる頂点と辺を順にたどり、\(\mathbf{r}\) の終点で終わる歩道を \(\mathbf{f}\) と \(\mathbf{r}\) の結合 (merge) と呼び、\(\mathbf{f} \;\widehat{\,\phantom{\text{\small l}}\,}\, \mathbf{r}\) と表記する¹。二つの歩道が結合可能なのは、一つ目の歩道の終点と二つ目の歩道の始点が一致するときに限られる。二つの歩道が結合される頂点を明示できると便利な場合もあるので、終点が \(v\) の歩道 \(\textbf{f}\) と始点が \(v\) の歩道 \(\textbf{r}\) の結合は \(\textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,v\,}\ \textbf{r}\) とも表記する。

次の補題は定義から直ちに分かる:

次項では、歩道に沿った移動を考えることでグラフの性質を証明する。

10.2.1 路の計算

どこかに早く移動したいとき、同じ場所を何度も通っていたら何かがおかしいと分かる。これはグラフ理論の基礎的な定理の主張そのものである。

証明 頂点 \(u\) から頂点 \(v \neq u\) への歩道が一つでも存在するなら、整列原理より \(u\) から \(v\) への最短歩道 \(\textbf{w}\) が存在する。この \(\textbf{w}\) が路だと背理法で証明する。

\(\textbf{w}\) が路でないと仮定する。このとき \(\textbf{w}\) に二回現れる頂点が存在する。その頂点を \(x\) とすれば、次の等式が成り立つ:

ここで \(\textbf{e}\), \(\textbf{f}\), \(\textbf{g}\) は歩道であり、\(\textbf{f}\) の長さは正である。このとき、\(\textbf{f}\) を「削除」して得られる歩道

は長さが \(\textbf{w}\) より小さく、かつ \(u\) から \(v\) への歩道である。これは \(\textbf{w}\) の最小性と矛盾する。 ■

「距離」という言葉の選択から想像できるように、この定義は次の性質を持つ:

この三角不等式の成立は当然だと思っても不思議ではない。しかし、ここでは「距離」が特別な意味を持つので証明が必要になる。例えば、空間における通常の距離と異なり、有向グラフでは \(u\) から \(v\) への距離が \(v\) から \(u\) への距離と一致しない。証明を次に示す:

証明 \(\textbf{f}\) を \(u\) から \(x\) への最短路、\(\textbf{r}\) を \(x\) から \(v\) への最短路とする。このとき補題 10.2.2 より \(\textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,x\,}\ \textbf{r}\) は \(u\) から \(v\) の歩道であり、その長さは \(\operatorname{dist}(u, x) + \operatorname{dist}(x, v)\) に等しい。よって定理 10.2.3 より、この和は \(u\) から \(v\) への最短路の長さの上界となる。

等号成立条件に関する議論は練習問題 (問題 10.3) とする。 ■

最後に、歩道と路の関係は閉歩道と閉路でも成り立つ:

補題 10.2.6 の証明は定理 10.2.3 の証明と本質的に同一である。詳細は練習問題 (問題 10.4) とする。