前回に続いて行列の計算についてみていこう．毎回同じ隣接行列を書くのはめんどうなので，駅の接続関係の隣接行列を\(M_{bahn}\)としよう．(Bahn はドイツ語で鉄道の意味)
\begin{eqnarray*} M_{bahn} &= & \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \end{eqnarray*}
\(M_{bahn}\) を一度駅ベクトルに掛けると隣接する駅が計算できる．二度掛けると2ステップで到達できる駅が計算できる．計算結果に出てくる数字は，各駅に到達できる道筋の数を示す．Weinmeisterstr にいるという駅ベクトルに二回\(M_{bahn}\) を掛けた結果は以下にようになる．
\begin{eqnarray*} (M_{bahn})^2 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \end{eqnarray*}
それぞれの要素が意味することは，それぞれの駅に 2 step で行く方法が何通りあるかということである．
\begin{eqnarray*} \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \begin{array}{cccc} \mbox{Wein.} & \rightarrow & \mbox{Wein.} & \mbox{2 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Alex.} & \mbox{2 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Hack.} & \mbox{1 通り} \\ \mbox{Wein.} & \rightarrow & \mbox{Jann.} & \mbox{1 通り} \\ \end{array} \end{eqnarray*} 例えば，Wein. から Wein. に 2 step で行く方法は Wein. \(\rightarrow\)Wein. \(\rightarrow\) Wein. (二度同じ駅に留まる) と Wein.\(\rightarrow\) Alex. \(\rightarrow\) Wein (Alex に行って戻る)である．
これを計算するプログラムとして私は octave [6] か matlab をおすすめする．私は個人的には matlab が好きなのであるが，個人の趣味として買うにはあまりに高すぎて手がでない．5 年古いバージョンでいいから，ツールキット込みで 100 Euro 位で売ってもらえれば買うのだが．Mathematica のHome Edition のようなものは出ないだろうか．octave の場合は以下のようになる．(以下，全ての octave の例では出力結果を Page のカラムに収まるように，あるいは空行を削るなどの多少の編集している．)
octave:6> Mb = [1 1 0 0; 1 1 1 1;
0 1 1 0; 0 1 0 1];
octave:7> w = [1 0 0 0]';
octave:8> Mb * w
ans =
1
1
0
0
octave:9> Mb * Mb * w
ans =
2
2
1
1
3回動いた場合はどうだろうか．
octave:10> Mb^3 * w
ans =
4
6
3
3
3 回動いて，Weinmeisterstr に到達する方法は 4 通りある．以下にそれを示す．ここで WはWeinmeisterstr, A は Alexanderplatz を示す．矢印が3つあるので3回動いた(あるいは留まった)ことを示す．
\begin{eqnarray*} \begin{array}{ccccccc} \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\ \end{array} \end{eqnarray*}
隣接行列を用いることで，何ステップ後にはどの駅にいることができるかということがわかった．
さて，なぜこうなるのかである．(以下は column space と解空間の関係を理解していることを仮定している．あまり詳しくない人はこの説明を飛ばしてしまってもかまわない．) まず第一に有向グラフの場合には行列をtranspose する必要がある．そうすると各カラムが隣接関係を示している．この場合，グラフはカラム数次元の空間を示すことになる．そうすると column space が示す空間こそが到達可能な場所になる．column space の線形結合を求めることは，すなわちベクトルを掛けることであった．したがって，それぞれの駅に何ステップで行けるかわかっている場合には，どこからスタートしたのかも計算できる．線形システムを解けばよい．しかし，どこの駅からスタートしたかはあまり興味のない問題だと思う．今どこにいて限られた時間でどこまで行けるかという方が通常は知りたいことだからである．
参考文献
[6] GNU Octave, http://www.gnu.org/software/octave/
Comments
Post a Comment