10.3 隣接行列

\(n\) 個の頂点 \(v_{0}\), \(v_{1}\), \(\ldots\), \(v_{n-1}\) を持つグラフ \(G\) は、隣接行列 (adjacency matrix) と呼ばれる \(n \times n\) 行列を使って表現すると有用な場合がある。\(G\) の隣接行列は\(A_{G}\) と表記され、その第 \(i\) 行 \(j\) 列要素 \((A_{G})_{ij}\) は頂点 \(v_{i}\) から頂点 \(v_{j}\) への辺が存在するなら \(1\) となり、そうでないなら \(0\) となる:

\[ (A_{G})_{ij} ::= \begin{cases} 1 & \langle v_{i} \to v_{j} \rangle \in E(G) \text{ のとき} \\ 0 & \text{それ以外のとき} \end{cases} \]

例えば、\(4\) 個の頂点を持つ図 \(\text{10.1}\) のグラフを \(H\) とするとき、\(H\) の隣接行列 \(A_{H}\) は次の \(4 \times 4 \) 行列である:

\[ A_{H} = \begin{array}{c|cccc|} & a & b & c & d \\ \hline a & 0 & 1 & 0 & 1 \\ b & 0 & 0 & 1 & 1 \\ c & 0 & 1 & 0 & 0 \\ d & 0 & 0 & 1 & 0 \end{array} \]

この表現を使うとき、特定の長さを持つ任意の二頂点間の歩道の個数は行列の乗算で計算できる。例えば、グラフ \(H\) には \(a\) から \(c\) への長さ \(2\) の歩道が二つある:

\[ \begin{alignedat}{5} &a\ &&\langle a \to b \rangle\ &&b\ &&\langle b \to c \rangle\ &&c \\ &a\ &&\langle a \to d \rangle\ &&d\ &&\langle d \to c \rangle\ &&c \\ \end{alignedat} \]

これ以外に \(a\) から \(c\) への長さ \(2\) の歩道は存在しない。また、\(b\) から \(c\) への長さ \(2\) の歩道はちょうど \(2\) 個あり、\(d\) から \(b\) への長さ \(2\) の歩道はちょうど \(1\) 個ある。こういった値は行列の二乗 \((A_{H})^{2}\) を計算することで求められる:

\[ (A_{H})^{2} = \begin{array}{c|cccc|} & a & b & c & d \\ \hline a & 0 & 0 & 2 & 1 \\ b & 0 & 1 & 1 & 0 \\ c & 0 & 0 & 1 & 1 \\ d & 0 & 1 & 0 & 0 \end{array} \]

一般に、任意の有向グラフ \(G\) の隣接行列の冪 \((A_{G})^{k}\) は任意の二頂点間の長さ \(k\) の歩道の個数を与える。この事実を証明しよう。まず用語を一つ定義する:

定義 10.3.1

\(G\) を \(n\) 個の頂点を持つ有向グラフとする。\(G\) の長さ \(k\) の歩道数え上げ行列 (length-\(k\) walk counting matrix) とは、次の規則で定義される \(n \times n\) 行列を言う:

\[ A_{uv} ::= u \text{ から } v \text{ への長さ } k \text{ の歩道の個数} \tag{10.4}\]

グラフ \(G\) の隣接行列 \(A_{G}\) は長さ \(1\) の歩道数え上げ行列に等しい。また、慣習的に恒等行列と定義される \((A_{G})^{0}\) は長さ \(0\) の歩道数え上げ行列に等しい。

定理 10.3.2

\(G\) を有向グラフとする。\(C\) が \(G\) の長さ \(k\) の歩道数え上げ行列で、\(D\) が \(G\) の長さ \(m\) の歩道数え上げ行列のとき、\(CD\) は \(G\) の長さ \(k + m\) の歩道数え上げ行列である。

この定理からは、グラフ \(G\) の隣接行列の二乗 \((A_{G})^{2}\) は \(G\) の長さ \(2\) の歩道数え上げ行列だと分かる。同様に \((A_{G})^{2} A_{G}\) を考えれば、長さ \(3\) の歩道数え上げ行列が \((A_{G})^{3}\) だと分かる。数学的帰納法を使えば、次の一般的な系が得られる:

系 10.3.3

任意の \(k \in \mathbb{N}\) と有向グラフ \(G\) に対して、\(G\) の長さ \(k\) の歩道数え上げ行列は \((A_{G})^{k}\) である。

言い換えれば、任意の二頂点間の長さ \(k\) の歩道の個数は隣接行列の \(k\) 乗を計算することで求められる！驚くべき事実だと思ったかもしれないが、証明では行列の乗算と歩道の個数の間にある単純な関係が利用される:

定理 10.3.2 の証明 \(u\) から \(v\) への長さ \(k + m\) の任意の歩道は、先頭部分に \(u\) から何らかの頂点 \(w\) への長さ \(k\) の歩道を持ち、その直後に \(w\) から \(v\) への長さ \(m\) の歩道を持つ。よって、\(k\) 番目の頂点が \(w\) であるような \(u\) から \(v\) への長さ \(k + m\) の歩道の個数は、\(u\) から \(w\) への長さ \(k\) の歩道の個数 \(C_{uw}\) と、\(w\) から \(v\) への長さ \(m\) の歩道の個数 \(D_{wv}\) の積に等しい。\(u\) から \(v\) への長さ \(k + m\) の歩道の個数は、\(k\) 番目の頂点が \(w\) である歩道の個数を全ての \(w\) に関して足すと得られる。言い換えれば、次の等式が成り立つ:

\[ u \text{ から } v \text{ への長さ } k + m \text{ の歩道の個数} = \sum_{w \in V(G)} C_{uw} \cdot D_{wv} \tag{10.5}\]

この等式の右辺は \((CD)_{uv}\) の定義に等しい。よって \(CD\) は長さ \(k + m\) の歩道数え上げ行列である。 ■

10.3.1 最短路

隣接行列の冪と歩道の個数の関係は (少なくとも私たち数学オタクにとって) クールであるものの、これよりもずっと重要な問題として二頂点間の最短路を見つける問題がある。例えば休日に車でどこかへ出かけるとき、普通は最も短い時間で到着する経路を利用するだろう。

\(n\) 頂点の有向グラフ \(G\) における任意の二頂点間の最短路の長さを求める単純な方法として、\(G\) の隣接行列 \(A_{G}\) の冪を \(n - 1\) 乗まで一つずつ計算し、各要素が初めて \(1\) になる瞬間を記録する方法がある。この方法の正しさは次の二つの事実から分かる:

\(u\) から \(v\) への最短路が存在するなら、その長さは \(u\) と \(v\) の距離であり、それは定理 10.3.2 より \((A_{G})_{uv}^{k}\) が \(0\) でない最小の自然数 \(k\) に等しい。
\(u\) から \(v\) への最短路が存在するなら、その長さは必ず \(n - 1\) 以下である。

このアイデアを発展させると、それなりに高速な最短路発見手法が得られる。その手法は重み付きグラフに対する同様の問題も適用できる: 辺に重み (コスト) が割り当てられたグラフが与えられ、重みが最小の (最もコストの安い) 路を求める問題である。こういった最短路問題に関する話題はアルゴリズムの入門講義で触れられることが多いので、本書ではこれ以上深入りしない。