グラフ行列
グラフの情報を行列に落とし込む方法が幾つかある。
グラフの頂点$ v_iに接続した辺の数$ \deg(v_i)を頂点$ v_iの字数という。
グラフの任意の頂点の次数を対角要素上に並べた対角行列を、次数行列と呼ぶ。 $ d_{i,j}:=\begin{cases}\deg(v_i)&{\rm if}\ i=j\\0&{\rm otherwise}\end{cases}
このグラフの場合、
https://gyazo.com/b855d3fd5a1c9c7453a5c5c332e0530b
この行列を得る
$ D=\begin{pmatrix}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\end{pmatrix}
2つの頂点$ v_i,v_jの間に辺$ e_{i,j}が張られていることを$ v_i,v_jは隣接するという。
辺$ e_{i,j}に付加されている数$ w_{i,j}を辺の重みという。
辺のない頂点間には重み$ 0の辺があるものとしてみなす。
辺の重み$ w_{i,j}を並べた行列を隣接行列という。 重みがない場合は、全ての辺の重みを$ 1として隣接行列を作成する。
このグラフの場合、
https://gyazo.com/b855d3fd5a1c9c7453a5c5c332e0530b
この行列を得る
$ A=\begin{pmatrix}0&a&0&0&e&0\\a&0&b&0&x&0\\0&b&0&c&0&0\\0&0&c&0&d&y\\e&x&0&d&0&0\\0&0&0&y&0&0\end{pmatrix}
https://gyazo.com/f4690c3498c9acf35376682c0391f367https://gyazo.com/b2080027c01c8e51db74760d55a17b6c
https://gyazo.com/0f2b5ab7840d0c87aaec82577bef02bfhttps://gyazo.com/0737bd15efef37ff9278bc52355566a5
隣接行列のべき乗を考えることがある。
$ A^2=\begin{pmatrix}0&a&0&0&e&0\\a&0&b&0&x&0\\0&b&0&c&0&0\\0&0&c&0&d&y\\e&x&0&d&0&0\\0&0&0&y&0&0\end{pmatrix}\begin{pmatrix}0&a&0&0&e&0\\a&0&b&0&x&0\\0&b&0&c&0&0\\0&0&c&0&d&y\\e&x&0&d&0&0\\0&0&0&y&0&0\end{pmatrix}
$ \begin{pmatrix}0&0&0&0&0&0\\0&a^2&0&0&ae&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&ea&0&0&e^2&0\\0&0&0&0&0&0\\\end{pmatrix}+\begin{pmatrix}a^2&0&ab&0&ax&0\\0&0&0&0&0&0\\ba&0&b^2&0&bx&0\\0&0&0&0&0&0\\xa&0&xb&0&x^2&0\\0&0&0&0&0&0\\\end{pmatrix}
$ +\begin{pmatrix}0&0&0&0&0&0\\0&b^2&0&bc&0&0\\0&0&0&0&0&0\\0&cb&0&c^2&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\\end{pmatrix}+\begin{pmatrix}0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&c^2&0&cd&cy\\0&0&0&0&0&0\\0&0&dc&0&d^2&dy\\0&0&yc&0&yd&y^2\\\end{pmatrix}
$ +\begin{pmatrix}e^2&ex&0&ed&0&0\\xe&x^2&0&xd&0&0\\0&0&0&0&0&0\\de&dx&0&d^2&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\\end{pmatrix}+\begin{pmatrix}0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&y^2&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\\end{pmatrix}
$ =\begin{pmatrix}a^2+e^2&ex&ab&ed&ax&0\\xe&a^2+b^2+x^2&0&bc+xd&ac&0\\ba&0&b^2+c^2&0&bx+cd&cy\\de&cb+dx&0&c^2+d^2+y^2&0&0\\xa&ea&xb+dc&0&e^2+x^2+d^2&dy\\0&0&yc&0&yd&y^2\end{pmatrix}
$ L=D-A
このグラフの場合、
https://gyazo.com/b855d3fd5a1c9c7453a5c5c332e0530b
この行列を得る
$ L=\begin{pmatrix}2&-a&0&0&-e&0\\-a&3&-b&0&-x&0\\0&-b&2&-c&0&0\\0&0&-c&3&-d&-y\\-e&-x&0&-d&3&0\\0&0&0&-y&0&1\end{pmatrix}
$ \because D-A=\begin{pmatrix}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\end{pmatrix}-\begin{pmatrix}0&a&0&0&e&0\\a&0&b&0&x&0\\0&b&0&c&0&0\\0&0&c&0&d&y\\e&x&0&d&0&0\\0&0&0&y&0&0\end{pmatrix}
$ {\rm sym}(L)=D^{-\frac12}LD^{-\frac12}
$ =D^{-\frac12}(D-A)D^{-\frac12}
$ =D^{-\frac12}DD^{-\frac12}-D^{-\frac12}AD^{-\frac12}
$ =I-D^{-\frac12}AD^{-\frac12}$ \because Dは対角行列 $ {\rm rw}(L)=D^{-1}L
$ =D^{-1}(D-A)
$ I-D^{-1}A