Graph Routes

Imagine a situation where there are 7 possible locations: 1, 2, ..., 7. There are one-way streets connecting various pairs. For example, if you can get from location 3 to location 7, there will be a street labelled $ (3, 7)$. Here is a complete list of the streets:

$ (1,2)$, $ (1, 7)$, $ (2,3)$, $ (2,4)$, $ (2,5)$, $ (3, 6)$, $ (4,5)$, $ (4,6)$, $ (5,6)$, $ (5,7)$, and $ (6,7)$, $ (7,1)$.

If you begin on location 1, and take 16 steps, how many different routes are there that put you on each of the locations? (The discussion that follows will be much easier to follow if you draw a picture. Make a circle of 7 dots, labelled 1 through 7, and for each of the pairs above, draw an arrow from the first dot of the pair to the second.)

This time, we can represent the number of paths to each location by a column vector:

$\displaystyle \begin{pmatrix}p_1\\ p_2\\ p_3\\ p_4\\ p_5\\ p_6\\ p_7\end{pmatrix}, $

where $ p_i$ is the number of paths to location $ i$. The initial vector for time=0 has $ p_1 = 1$ and $ p_2=p_3=p_4=p_5=p_6=p_7=0$. In other words, after zero steps, there is exactly one path to location 1, and no paths to other locations. You can see that if you multiply that initial vector by the matrix once, it will show exactly one path to 2 and one path to 7 and no other paths.

The transition matrix looks like this:

$\displaystyle \begin{pmatrix}0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0... ...d{pmatrix} \begin{pmatrix}p_1\\ p_2\\ p_3\\ p_4\\ p_5\\ p_6\\ p_7\end{pmatrix}.$ (4)

which will generate the count of the number of paths in $ n+1$ steps if the input is the number of paths at step $ n$.

If the matrix on the left of equation (4) is called $ P$, then after 16 steps, the counts will be given by:

$\displaystyle P^{16} \begin{pmatrix}p_1\\ p_2\\ p_3\\ p_4\\ p_5\\ p_6\\ p_7\end{pmatrix}. $

>From a computer, here is $ P^{16}$:

$\displaystyle \begin{pmatrix} 481 & 440 & 104 & 280 & 292 & 188 & 288 \\ 288 &... ...1 & 280 & 173 & 264 \\ 728 & 676 & 188 & 480 & 476 & 288 & 481 \end{pmatrix}. $

Since initially $ p_1 = 1$ and $ p_2=p_3=p_4=p_5=p_6=p_7=0$, we have:

$\displaystyle P^{16} \begin{pmatrix}p_1\\ p_2\\ p_3\\ p_4\\ p_5\\ p_6\\ p_7\end... ...trix} = \begin{pmatrix} 481\\ 288\\ 188\\ 188\\ 292\\ 384\\ 728 \end{pmatrix}, $

so there are 481 routes to location 1, 288 routes to location 2, 188 routes to location 3, and so on.

This is, of course, very difficult to check. Why don't you check the results for $ P^3$--three step routes. The corresponding equation for only 3 steps is:

$\displaystyle P^{16} \begin{pmatrix}p_1\\ p_2\\ p_3\\ p_4\\ p_5\\ p_6\\ p_7\end... ...\end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 3 \\ 2 \end{pmatrix}. $

So there is no way to get to location 1 in three steps, one way to get to location 2: $ (1 \rightarrow 7 \rightarrow 1 \rightarrow 2)$, no ways to get to locations 3 or 4, one way to get to location 5: $ (1 \rightarrow 2 \rightarrow 4 \rightarrow 5)$, three ways to get to location 6: $ (1 \rightarrow 2 \rightarrow 3 \rightarrow 6)$, $ (1 \rightarrow 2 \rightarrow 4 \rightarrow 6)$, and $ (1 \rightarrow 2 \rightarrow 5 \rightarrow 6)$, and finally, two ways to get to location 7: $ (1 \rightarrow 2 \rightarrow 5 \rightarrow 7)$ and $ (1 \rightarrow 7 \rightarrow 1 \rightarrow 7)$.

Obviously, there is nothing special about the set of paths and number of locations in the problem above. For any given setup, you just need to work out the associated transition matrix and you're in business. Even if there are ``loops''--paths that lead from a location to itself--there is no problem. A loop will simply generate an entry of 1 in the diagonal of the transition matrix.