Last time I forgot to tell you about the diagonal element of the matrix. In the last article, the diagonal elements of the adjacency matrix are zero. That means you can not stay the station. However, I think each station is connected to itself. It seems not so reasonable if someone want to stay the station, one always need to move one station and come back. When you want to force such move, then, this adjacency matrix is useful. However, if I want to go to Alexanderplatz from Alexanderplatz, which means I want to stay at Alexanderplatz, I just want to stay the station. If we allow to stay at a station, the adjacency matrix should be the following.

\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*} The diagonal elements are now 1.

An adjacency matrix doesn't only show the connections, but also we can compute which station we can reach. This is a nice property of the adjacency matrix. For example, if I am at the Weinmeisterstr and then let's compute where can I reach in one step. We can represent the current location as a following vector.

\begin{eqnarray*} \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] \end{eqnarray*} This vector means someone is at Weinmeisterstr strasse, and no one is other stations.

I just call this vector as station vector, since this vector represents how many possibility to visit to a specific station. Now we apply the adjacency matrix to this station vector.

\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*}

The first element of the vector represents possible visiting number of method to Weinmeisterstr, and the second element of the vector represents possible visiting number of method to Alexanderplatz. These are 1, that means one step after started with Weinmeisterstr, we can be at Weinmeisterstr or Alexanderplatz. In other words, If we move one step from Weinmeisterstr, we can reach Weinmeisterstr or Alexanderplatz. When we want to visit Weinmeisterstr from Weinmeisterstr in one step, we can just stay the station.

You now see the power of matrix. At the first point, we only know the connections between stations. But we can now compute the where we can go. We will see more about the adjacency matrix.

## No comments:

Post a Comment