隣接行列の一般化とトロピカル演算の正体 - 現実と数学の区別が付かない

最近話題になったこの記事。
qiita.com

この記事は主に次の事実を扱ったものです。

有向グラフの辺の重みを並べた行列のトロピカルな $m$ 乗の第 $(i, j)$ -成分は， $i$ 番目の頂点から $j$ 番目の頂点への道のうち，最小の重みを持つものの重みに等しいという話です。

ここで，トロピカル演算は次のように定義されるものです。

トロピカル加法 $a\oplus b := \min\{a,b\}$
トロピカル乗法 $a\otimes b :=a+b$
トロピカル加法の単位元 $\infty \oplus a =a \oplus \infty=a, \infty \otimes a =a \otimes \infty=\infty$

この話を聞いて，似た話を知っていると思った人もいたのではないでしょうか。それは次の定理です。

有向グラフの隣接行列の $m$ 乗の第 $(i, j)$ -成分は， $i$ 番目の頂点から $j$ 番目の頂点への道の数に等しい。

辺の重みを並べた行列は，隣接行列に見た目がよく似ています。

この2つの似た事実は成り立つ理由もよく似ていますが，隣接行列をうまく一般化するとこの2つの事実を同時に示すことができるというのが今日のお話です。この話を通して，トロピカル演算の正体が見えてきます。

2つの類似した現象
隣接行列の一般化
- 具体例
- 隣接行列・重み行列との関係
トロピカル演算の正体

2つの類似した現象

以降では自己ループや多重辺も許容する有向グラフ $G=(V,E)$ を考えます。ただし， $V=\{1,\dots,n\}$ を頂点集合， $E$ を辺集合とします。また，辺 $e\in E$ に対し， $e$ の始点を $s(e)$ ，終点を $t(e)$ で表すことにします*1。

有向グラフの隣接行列

さて，有向グラフ $G=(V,E)$ に対して
\begin{align}
a_{ij}&=\#\{e\in E \mid s(e)=i, t(e)=j\}\\
&=\mbox{頂点$i$ から頂点$j$ への辺の本数}
\end{align}で定まる $n\times n$ 行列 $A=(a_{ij})_{i,j\in V}$ を $G$ の隣接行列と呼びます。

隣接行列 $A$ の $m$ 乗 $A^m$ の第 $(i, j)$ -成分は

$\displaystyle \sum_{k_1,k_2,\dots,k_{m-1} \in V} a_{i k_1} a_{k_1k_2} a_{k_2k_3} \dots a_{k_{m-1} j}$

です。 $a_{k\ell}$ は頂点 $k$ から頂点 $\ell$ への辺の本数なので， $\sum$ の中身は

$\displaystyle i\rightarrow k_1 \rightarrow k_2 \rightarrow \dots \rightarrow k_{m-1} \rightarrow j$

というルートを通る道の本数を表しています。よって，その合計は $i$ から $j$ への長さ $m$ の道の数に等しいことが分かります。

有向グラフの重み行列

さらに，辺の重みを与える関数 $w:E\to \mathbb{Z}_{\ge 0}$ が定まっている場合を考えましょう。つまり，各辺 $e\in E$ に重み $w(e)\in \mathbb{Z}_{\ge 0}$ が定まっています。

応用上では重みは，辺の長さや，通過にかかる時間・コスト，容量などを表すものとして定められることが多いです。

辺に重みがつけられた有向グラフ $G=(V,E)$ に対して，
\begin{align}
w_{ij}&=\min\{w(e)\mid e\in E,s(e)=i, t(e)=j \}\\
&=\mbox{頂点$i$ から頂点$j$ への辺の重みの最小値}
\end{align}で定まる $n\times n$ 行列 $W=(w_{ij})_{i,j\in V}$ を $G$ の重み行列と呼びます。ただし， $i$ から $j$ への辺がないときは $w_{ij}=\infty$ と定めます。これは重みが辺の通過にかかる時間を表しているとき，「辺がない」ことを「時間が無限にかかる」と表現していると解釈すれば，この定義に納得できると思います。

重み行列 $W$ のトロピカルな $m$ 乗 $W^{\otimes m}$ の第 $(i, j)$ -成分は

$\displaystyle \bigoplus_{k_1,k_2,\dots,k_{m-1} \in V} a_{ik_1}\otimes w_{k_1k_2}\otimes w_{k_2k_3}\otimes \dots \otimes w_{k_{m-1}k_m} \otimes w_{k_m j}\hspace{20mm}$
$\displaystyle= \min\{ w_{ik_1}+ w_{k_1k_2}+ w_{k_2k_3}+\dots+ w_{k_{m-1}j} \mid k_1,k_2,\dots,k_{m-1} \in V \}$

です。 $w_{k\ell}$ は頂点 $k$ から頂点 $\ell$ への辺の重みの最小値なので， $\min$ の中身は

$\displaystyle i\rightarrow k_1 \rightarrow k_2 \rightarrow \dots \rightarrow k_{m-1} \rightarrow j$

というルートを通る道の重みの最小値を表しています。よってその最小値は $i$ から $j$ への長さ $m$ の道の重みの最小値に等しいことが分かります。

具体例

具体例で見てみましょう。

f:id:egory_cat:20190713093829p:plain:w300

この有向グラフの隣接行列 $A$ と重み行列 $W$ は
\begin{align}
A=\left(
\begin{array}{ccccc}
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0
\end{array}
\right),~~~
W=\left(
\begin{array}{ccccc}
\infty & 3 & \infty & \infty & \infty\\
\infty & \infty & 2& \infty & 7\\
6 & \infty & \infty & \infty & \infty \\
\infty &10 & \infty & \infty & \infty \\
\infty & \infty & 5 & 1 & \infty
\end{array}
\right)
\end{align}となります。この $6$ 乗をそれぞれ計算してみましょう。ただし $W$ の方はトロピカルな $6$ 乗です。

\begin{align}
A^6=\left(
\begin{array}{ccccc}
2 & 0 & 3 & 2 & 1\\
3 & 4 & 1 & 1 & 0\\
0 & 1 & 2 & 0 & 2\\
2 & 0 & 3 & 2 & 1\\
1 & 3 & 2 & 0 & 2
\end{array}
\right),~~~
W^{\otimes 6}=\left(
\begin{array}{ccccc}
{22} & \infty & {26} & {22} & {31}\\
{29} & {22} & {33} & {29} & \infty\\
\infty & {30} & {22} & \infty & {27}\\
{29} & \infty & {33} & {29} & {38}\\
{32} & {25} & {24} & \infty & {29}
\end{array}
\right)
\end{align}
$A^6$ の第 $(1, 4)$ -成分は $2$ なので，頂点 $1$ から頂点 $4$ への長さ $6$ の道はちょうど $2$ 本あることが分かります。

また， $W^{\otimes 6}$ の第 $(1, 4)$ -成分は $22$ なので，頂点 $1$ から頂点 $4$ への長さ $6$ の道の最小の重みは $22$ であることが分かります。

実際，頂点 $1$ から頂点 $4$ への長さ $6$ の道は\begin{align}
&1\rightarrow2\rightarrow3\rightarrow1\rightarrow2\rightarrow5\rightarrow4\\
&1\rightarrow2\rightarrow5\rightarrow4\rightarrow2\rightarrow5\rightarrow4
\end{align}の $2$ 本だけで，重みはそれぞれ \begin{align} 3+2+6+3+7+1&=22\\3+7+1+10+7+1&=29\end{align} になっており，最小値は確かに $22$ です。

隣接行列の一般化

さて， $A$ と $W$ 両方の情報を含むような新たな行列を定義しましょう。

$G=(V,E)$ は $V=\{1,\dots,n\}$ を頂点集合， $E$ を辺集合とする自己ループや多重辺も許容する有向グラフで，重み関数 $w:E\to \mathbb{Z}_{\ge 0}$ が定まっていたことを思い出しましょう。また， $e\in E$ は $s(e)$ から $t(e)$ への辺です。

$x$ を変数とし，\begin{align}
a_{ij}(x)=\sum_{e\in E, s(e)=i,t(e)=j} x^{w(e)}
\end{align}で定まる $n\times n$ 行列 $A(x)=(a_{ij}(x))_{i,j\in V}$ を $G$ の多項式隣接行列と呼ぶことにします。

多項式隣接行列 $A(x)$ の $m$ 乗 $A(x)^m$ の第 $(i, j)$ -成分は

$\displaystyle \sum_{k_1,k_2,\dots,k_{m-1} \in V} a_{i k_1}(x) a_{k_1k_2}(x) a_{k_2k_3}(x) \dots a_{k_{m-1} j}(x)$

です。この展開を考えると， $A(x)^m$ の第 $(i, j)$ -成分の $x^d$ の係数は， $i$ から $j$ への長さ $m$ の道で，重みが $d$ であるものの本数であることが分かります。

具体例

先ほどの例で見てみましょう。

この有向グラフの多項式隣接行列は

$A(x)=\left( \begin{array}{ccccc} 0 & x^3 & 0 & 0 & 0\\ 0 & 0 & x^2 & 0 & x^7\\ x^6 & 0 & 0 & 0 & 0\\ 0 & x^{10} & 0 & 0 & 0\\ 0 & 0 & x^5 & x & 0 \end{array} \right)$

となります。この $6$ 乗を計算してみましょう。

$A(x)^6=\left( \begin{array}{ccccc} x^{29}+x^{22} & 0 & x^{33}+2x^{26} & x^{29}+x^{22} & x^{31}\\ x^{36}+2x^{29} & x^{36}+2x^{29}+x^{22} & x^{33} & x^{29} & 0\\ 0 & x^{30} & x^{29}+x^{22} & 0 & x^{34}+x^{27}\\ x^{36}+x^{29} & 0 & x^{40}+2x^{33} & x^{36}+x^{29} & x^{38}\\ x^{32} & 2x^{32}+x^{25} & x^{31}+x^{24} & 0 & x^{36}+x^{29} \end{array} \right)$

$A(x)^6$ の第 $(1, 4)$ -成分は $x^{29}+x^{22}$ なので，頂点 $1$ から頂点 $4$ への長さ $6$ の道は，重みが $29$ のものと $22$ のものが $1$ 本ずつあることが分かります。

また，第 $(2, 2)$ -成分は $x^{36}+2x^{29}+x^{22}$ なので，頂点 $2$ から頂点 $2$ への長さ $6$ の道は，重みが $36$ のものと $22$ のものが $1$ 本ずつ，重みが $29$ のものが $2$ 本あることが分かります。

実際，\begin{align}
&2\rightarrow5\rightarrow4\rightarrow2\rightarrow5\rightarrow4\rightarrow2\\
&2\rightarrow3\rightarrow1\rightarrow2\rightarrow3\rightarrow1\rightarrow2\\
&2\rightarrow5\rightarrow4\rightarrow2\rightarrow3\rightarrow1\rightarrow2\\
&2\rightarrow3\rightarrow1\rightarrow2\rightarrow5\rightarrow4\rightarrow2
\end{align}の $4$ 本で，重みがそれぞれ $36,22,29,29$ となっています。

隣接行列・重み行列との関係

定義より， $A(x)$ に $x=1$ を代入したものは隣接行列 $A$ に一致しています。よって， $A^m$ は $A(x)^m$ に $x=1$ を代入することで得られます。

また， $W^{\otimes m}$ の第 $(i, j)$ -成分は $i$ から $j$ への長さ $m$ の道の重みの最小値でしたが，これは $A(x)^m$ の第 $(i, j)$ -成分の最低次数に一致します (ただし， $0$ の最低次数は $\infty$ と約束します)。

こうしてみると，トロピカル演算の正体が見えてきます。つまりトロピカル演算とは，多項式の最低次数だけを抜き出して計算しているものなのです。

トロピカル演算の正体

多項式 $\displaystyle f(x) = \sum_n c_nx^n$ に対し，\begin{align}\mathrm{ord}(f)&:=\min \{n \mid c_n\neq 0\}\\ \mathrm{ord}(0)&:=\infty \end{align} と定義し， $f(x)$ のオーダーと呼びます。

$\mathrm{ord}(0)=\infty$ とする理由を説明します。いま，次数の小さい部分に注目していますが，これは $|x|$ が十分に小さい範囲を考えていることに対応しています。物理学で， $|x|$ が十分に小さいときに $\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\cdots$ を $x$ で近似したりしますよね。 $|x|$ が十分に小さいときは $\displaystyle \lim_{n\to \infty} x^n=0$ なので， $\mathrm{ord}(0)=\infty$ と約束するのが都合がよいのです。

$2$ つの多項式 $\displaystyle f(x), g(x)$ に対し， \begin{align}
\mathrm{ord}(fg)&=\mathrm{ord}(f)+\mathrm{ord}(g)\\
\mathrm{ord}(f+g)&\ge \min\{\mathrm{ord}(f),~\mathrm{ord}(g)\}\\
\end{align}が成り立ちます。2番目の不等式で等号が成り立たないのは，最低次数の部分がちょうどキャンセルして $0$ になる場合です。

よってそれ以外の場合，例えば $f$ と $g$ の係数が全て非負の場合は \begin{align}
\mathrm{ord}(fg)&=\mathrm{ord}(f)+\mathrm{ord}(g)\\
\mathrm{ord}(f+g)&= \min\{\mathrm{ord}(f),~\mathrm{ord}(g)\}\\
\end{align}となります。オーダー関数 $\mathrm{ord}$ によって，加法が $\min$ に，乗法が $+$ に変換されていることが見て取れます。さらに加法単位元 $0$ については $\mathrm{ord}(0)=\infty$ で， $\mathrm{ord}(f\times 0)=\infty$ です。これはまさにトロピカル演算

を表しています。

より詳しくトロピカル代数・トロピカル幾何を知りたい方は次のサイトからいろいろたどってみてください。
http://pantodon.shinshu-u.ac.jp/topology/literature/tropical_mathematics.html

*1:つまり $E$ は単なる有限集合で， $2$ つの関数 $s:E\to V,~t:E\to V$ が定まっているということです。 $E$ の要素 $e\in E$ のことを $s(e)$ から $t(e)$ への辺と呼ぶことにします。自己ループや多重辺も許容するというのは， $s(e)=t(e)$ となる辺 $e$ があってもいいし，異なる辺 $e_1\neq e_2$ で $s(e_1)=s(e_2), t(e_1)=t(e_2)$ となるものがあってもいいといことです