前回ちょっと言い忘れてしまったことがある．それは隣接行列の対角成分をどうするかである．今回は駅には駅自身が接続されていると考えてもかまわないと思う．Alexanderplatz から Alexanderplatz へ行く場合，必ずどこか他の駅に行かなくてはならない場合には，上記の隣接行列は有用である．しかし．Alexanderplatz から Alexanderplatz へ行く場合，その駅に留まっても良い場合，には以下の隣接行列が使えるだろう．
\begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 1\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*} 隣接行列は接続を示すだけではない．行列の演算によってどの駅からどの駅に行けるかがわかるところがまたすばらしい．たとえば，Weinmeisterstr にいるとして，次にどこに行けるか計算してみよう．Weinmeisterstr にいるということを以下のベクトルで示すことができる．これはいまいる場所を 1 として他を0としたベクトルである．
\begin{eqnarray*} \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} このベクトルを駅を訪れる可能な方法の回数ということを示すベクトルという意味で駅ベクトルと呼ぶことにしよう．この駅ベクトルに隣接行列を掛けてみると，
\begin{eqnarray*} \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} になる．ベクトルの最初の要素は Weinmeisterstr であり，二番目の要素はAlexanderplatz であった．これら2つが 1 になったということは，これらの駅を訪れることができたということである．つまり Weinmeisterstr から1回動いて行ける駅は，Weinmeisterstr と Alexanderplatz である．Weinmeisterstr からWeinmeisterstr に行くには駅に留まっていればよい．これが行列の演算の効果である．知らなかったことを計算によって知ることができた．ここでは接続関係から，どの駅を訪れることができるかが計算できた．
\begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 1\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*} 隣接行列は接続を示すだけではない．行列の演算によってどの駅からどの駅に行けるかがわかるところがまたすばらしい．たとえば，Weinmeisterstr にいるとして，次にどこに行けるか計算してみよう．Weinmeisterstr にいるということを以下のベクトルで示すことができる．これはいまいる場所を 1 として他を0としたベクトルである．
\begin{eqnarray*} \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} このベクトルを駅を訪れる可能な方法の回数ということを示すベクトルという意味で駅ベクトルと呼ぶことにしよう．この駅ベクトルに隣接行列を掛けてみると，
\begin{eqnarray*} \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} になる．ベクトルの最初の要素は Weinmeisterstr であり，二番目の要素はAlexanderplatz であった．これら2つが 1 になったということは，これらの駅を訪れることができたということである．つまり Weinmeisterstr から1回動いて行ける駅は，Weinmeisterstr と Alexanderplatz である．Weinmeisterstr からWeinmeisterstr に行くには駅に留まっていればよい．これが行列の演算の効果である．知らなかったことを計算によって知ることができた．ここでは接続関係から，どの駅を訪れることができるかが計算できた．
次回は隣接行列のこの力をもっと見ていくことにしよう．
Comments
Post a Comment