隣接行列と道の数

三角形の頂点に $1,2,3$ と番号をつける。点が頂点 $1$ から出発し、毎回、辺を 1 本たどって別の頂点へ移る。$n$ 回移ったあとに頂点 $1$ にいる道順の数を数える。

• $n=1$：$1$ から移ると $2$ か $3$ にいるので、$0$ 通り。
• $n=2$：$1\to2\to1$、$1\to3\to1$ の $2$ 通り。
• $n=3$：$1\to2\to3\to1$、$1\to3\to2\to1$ の $2$ 通り。
• $n=4$：$1\to2\to1\to2\to1$、$1\to2\to1\to3\to1$、$1\to3\to1\to2\to1$、$1\to3\to1\to3\to1$、$1\to2\to3\to2\to1$、$1\to3\to2\to3\to1$ の $6$ 通り。
  毎回 2 通りの移り方があるので、$n$ 回移る道順は全部で $2^n$ 通りある。$n=4$ では $16$ 通りのうち $6$ 通りが頂点 $1$ に戻る。$n=10$ なら全部で $1024$ 通りあり、書き並べるのは難しい。

1 回に 1 段か 2 段ずつ上って、$n$ 段の階段を上りきる上り方の数を数える。$n=1$ は「1」の $1$ 通り、$n=2$ は「1,1」「2」の $2$ 通り、$n=3$ は「1,1,1」「1,2」「2,1」の $3$ 通り、$n=4$ は「1,1,1,1」「1,1,2」「1,2,1」「2,1,1」「2,2」の $5$ 通りである。
最初の 1 回が 1 段なら残り $n-1$ 段、2 段なら残り $n-2$ 段を上るので、$n$ 段の上り方の数を $s_n$ とすると $s_n=s_{n-1}+s_{n-2}$ である。$1,2,3,5,8,\dots$ は Fibonacci数 の並びである。この上り方も、後で図の上の道順として数え直す（ex-amw-stairs-as-walks）。

1. 三角形のグラフ（ex-amw-triangle-hand、図1 の左）では、異なる 2 頂点はどれも 1 本の辺で結ばれ、ループはないので
   $$ A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}. $$
2. 頂点 $1,2,3$ を一列に並べ、$1$–$2$、$2$–$3$ を結んだグラフ（図1 の中央）では $B=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$ である。$1$ と $3$ は直接結ばれていないので $b_{13}=0$ である。
3. 頂点 $1$ にループが 1 本あり、$1$–$2$ を 1 本の辺で結んだグラフ（図1 の右）では $C=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ である。
4. Königsberg の橋のグラフ（一筆書きとグラフ。陸地 $A,B,C,D$ を順に $1,2,3,4$ とする）では、$A$–$B$ と $A$–$C$ が 2 本ずつ、$A$–$D$、$B$–$D$、$C$–$D$ が 1 本ずつなので
   $$ K=\begin{pmatrix}0&2&2&1\\2&0&0&1\\2&0&0&1\\1&1&1&0\end{pmatrix}. $$
   ループのないグラフでは、第 $i$ 行の成分の和が頂点 $i$ の次数になる。$K$ の第 1 行の和は $0+2+2+1=5$ で、$A$ の次数 $5$ と一致する。

ex-amw-adjacency の 1 の $A$ について
$$ A^2=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}=\begin{pmatrix}0+1+1&0+0+1&0+1+0\\0+0+1&1+0+1&1+0+0\\0+1+0&1+0+0&1+1+0\end{pmatrix}=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix} $$
である。$(A^2)_{11}=2$ は ex-amw-triangle-hand の $n=2$ の $2$ 通り（$1\to2\to1$、$1\to3\to1$）と一致する。$(A^2)_{12}=1$ は、$1$ から $2$ への長さ $2$ の道筋が $1\to3\to2$ の 1 通りだけであることを表す。さらに
$$ A^3=A^2A=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}=\begin{pmatrix}2&3&3\\3&2&3\\3&3&2\end{pmatrix} $$
で、$(A^3)_{11}=2$ も $n=3$ の $2$ 通りと一致する。たとえば $(1,1)$ 成分は $2\cdot0+1\cdot1+1\cdot1=2$、$(1,2)$ 成分は $2\cdot1+1\cdot0+1\cdot1=3$ である。

ex-amw-adjacency の 4 の $K$ について、$K^2$ の $(1,1)$ 成分は
$$ (K^2)_{11}=0\cdot0+2\cdot2+2\cdot2+1\cdot1=9 $$
である。thm-amw-walks によれば、陸地 $A$ から出て橋を 2 回渡って $A$ に戻る道順が $9$ 通りある。実際、$A\to B\to A$ は行きの橋が 2 本、帰りの橋が 2 本で $2\times2=4$ 通り、$A\to C\to A$ も $4$ 通り、$A\to D\to A$ は $1$ 通りで、合わせて $9$ 通りである。同じ橋を行きと帰りに使う道順も数えている。

prop-amw-triangle の式で、$n=1,\dots,6$ の値を計算すると次のようになる。

$n=1,2,3,4$ の $(A^n)_{11}$ は、ex-amw-triangle-hand で書き並べた $0,2,2,6$ と一致する。どの $n$ でも $(A^n)_{11}+(A^n)_{12}+(A^n)_{13}=\frac{2^n+2(-1)^n}3+2\cdot\frac{2^n-(-1)^n}3=2^n$ で、頂点 $1$ から出る長さ $n$ の道筋の総数 $2^n$ に等しい。$n=10$ では $(A^{10})_{11}=\frac{1024+2}3=342$ で、$1024$ 通りを書き並べなくても求まる。

ex-amw-stairs の階段の上り方は、このグラフで頂点 $1$ から頂点 $1$ に戻る道筋と 1 対 1 に対応する。
段 1（対応のつけ方）。頂点 $1$ から出た道筋は、各時点で次のどちらかをする。(a) ループを 1 回たどって $1$ に戻る（長さ $1$）。(b) $1\to2$ と進む。頂点 $2$ から出る辺は $1$–$2$ の 1 本だけなので、(b) の次は必ず $2\to1$ と戻り、$1\to2\to1$ で長さ $2$ になる。よって、$1$ から $1$ への道筋は「長さ $1$ の (a)」と「長さ $2$ の (b)」を並べたものとしてただ 1 通りに書ける。(a) を「1 段」、(b) を「2 段」と読みかえると、長さ $n$ の道筋は $n$ 段の階段の上り方にちょうど対応する。
段 2（数える）。thm-amw-walks と prop-amw-fibonacci から、$1$ から $1$ への長さ $n$ の道筋の数は $(C^n)_{11}=F_{n+1}$ である。よって $n$ 段の上り方は $F_{n+1}$ 通りである。$n=4$ では
$$ C^4=\begin{pmatrix}5&3\\3&2\end{pmatrix} $$
で、$(C^4)_{11}=5=F_5$ が ex-amw-stairs の $5$ 通りと一致する。対応を具体的に書くと、「1,1,2」は $1\to1\to1\to2\to1$、「2,2」は $1\to2\to1\to2\to1$ である。

1. 三角形のグラフ：ex-amw-triangle-powers から $\operatorname{tr}A^3=2+2+2=6$ で、三角形は $6\mathbin{÷}6=1$ 個である。$\operatorname{tr}A^2=2+2+2=6=2\times3$ で、辺は $3$ 本である。
2. 4 頂点のどの 2 つも辺で結んだグラフ（四面体の頂点と辺）：計算すると $\operatorname{tr}A^3=24$ で、三角形は $4$ 個（四面体の 4 つの面）である。
3. 正八面体の頂点と辺のグラフ：$\operatorname{tr}A^3=48$ で、三角形は $8$ 個（正八面体の 8 つの面）である。
4. 一筆書きとグラフ の家の形（辺 $10$ 本）：$\operatorname{tr}A^2=20=2\times10$、$\operatorname{tr}A^3=30$ で、三角形は $5$ 個である。実際、$P_1P_2O$、$P_2P_3O$、$P_3P_4O$、$P_4P_1O$ と屋根の $P_4RP_3$ の 5 つである。

Königsberg のグラフ（ex-amw-konigsberg）では $(K^2)_{11}=9$ だが、陸地 $A$ の次数は $5$ である。長さ $2$ の閉じた道筋 $A\to B\to A$ は、行きと帰りの橋の選び方が $2\times2=4$ 通りあり、次数の数え方（$A$–$B$ の橋は $2$ 本）より多く数えられるからである。一般に $(A^2)_{ii}=\sum_k a_{ik}^2$ で、これが $\sum_ka_{ik}$（次数）に等しいのは、すべての $a_{ik}$ が $0$ か $1$ のときである。
満たす性質：ループはない。満たさない性質：2 頂点を結ぶ辺が高々 1 本。破る主張：prop-amw-trace の 1。

prop-amw-fibonacci の $C$ では、$C^3=\begin{pmatrix}F_4&F_3\\ F_3&F_2\end{pmatrix}=\begin{pmatrix}3&2\\2&1\end{pmatrix}$ で、$\operatorname{tr}C^3=4$ は $6$ の倍数ではない。頂点は 2 つしかないので三角形は $0$ 個である。$4$ 本の閉じた道筋は $1\to1\to1\to1$（ループを 3 回）、$1\to1\to2\to1$、$1\to2\to1\to1$、$2\to1\to1\to2$ で、どれもループを通る。
満たす性質：2 頂点を結ぶ辺は高々 1 本。満たさない性質：ループがない。破る主張：prop-amw-trace の 2。

三角形のグラフで $(A^3)_{12}=3$（ex-amw-triangle-powers）である。頂点 $1$ から $2$ への長さ $3$ の道筋は $1\to2\to1\to2$、$1\to2\to3\to2$、$1\to3\to1\to2$ の 3 本で、どれも同じ頂点を 2 度通っている。長さ $3$ の道で 4 つの頂点がすべて異なるものは、頂点が 3 つしかないので存在しない。つまり、同じ頂点を 2 度通らない道の数は $0$ で、$(A^3)_{12}=3$ とは違う。
同じ頂点を 2 度通らない道の数は、隣接行列の累乗では数えられない。すべての頂点をちょうど 1 回ずつ通る道（Hamilton閉路 の仲間）があるかどうかの判定が難しいことは、一筆書きとグラフ の「大学数学で見ると」で述べた。
満たす性質：thm-amw-walks の仮定はすべて満たす。破る主張：「$A^n$ の成分は、同じ頂点を通らない道の数でもある」という読み違い。

ex-amw-adjacency の 2 の $B$ について
$$ B^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix},\qquad B^3=B^2B=\begin{pmatrix}0&2&0\\2&0&2\\0&2&0\end{pmatrix}=2B $$
である。$B^3=2B$ から、$B^{2r+1}=2^rB$、$B^{2r+2}=2^rB^2$（$r\ge0$）が $r$ についての帰納法で出る（$B^{2r+3}=B^{2r+1}B^2=2^rB^3=2^{r+1}B$、$B^{2r+4}=B^{2r+3}B=2^{r+1}B^2$）。よって、奇数の $n$ では $(B^n)_{13}=0$、偶数の $n$ では $(B^n)_{12}=0$ で、どんなに長くしても、すべての成分が正になる $n$ はない。
理由は色分けで分かる。頂点 $1,3$ を白、$2$ を黒に塗ると、どの辺も白と黒を結ぶので、1 歩ごとに色が変わる。白の $1$ から白の $3$ へは偶数歩、黒の $2$ へは奇数歩でしか行けない。一方、三角形のグラフでは、ex-amw-triangle-formula の表のとおり $n\ge2$ で $A^n$ の成分はすべて正である。三角形があると、1 周 $3$ 歩（奇数）で戻れるので、偶奇のずれが起こらない。三角形がなくても、五角形のように奇数の長さで 1 周できれば、偶奇のずれは起こらない。このように頂点を 2 色に塗り分けて、どの辺も異なる色を結ぶようにできるグラフを 二部グラフ という。
満たす性質：連結である。満たさない性質：奇数の長さの閉じた道筋がある。破る主張：「長い道筋なら、どの 2 頂点の間にもある」。