Finding number of paths between vertices in a graph
According to my book, this is how it's done:
What exactly does $A^r$ represent?
Here is an example they did and I have no clue where all those 8s and 0s came from..
$\endgroup$ 12 Answers
$\begingroup$To help illustrate why the entries in the matrix equal the number of paths lets consider its application on a particular vector.
We have vertices $a,b,c,d$ each of which are represented by collumn vectors:
$$ a = \left[ \begin{array} \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right] b = \left[ \begin{array} \\ 0 \\ 1 \\ 0 \\ 0 \end{array} \right] c = \left[ \begin{array} \\ 0 \\ 0 \\ 1 \\ 0 \end{array} \right] d = \left[ \begin{array} \\ 0 \\ 0 \\ 0 \\ 1 \end{array} \right] $$
A useful heuristic in this problem is to think of the entry in the vector as describing the location of a point traversing the graph. The vector $[1,0,0,0]$ would represent the point being at vertice $a$. Applying the adjacency matrix to this vector causes the point to split and travel along each edge to the adjacent vertices.
We can see this by multiplying the vector for $a$ by the adjacency matrix,
$$ Aa= \left[\begin{array} \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array}\right] \left[ \begin{array} \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right] = \left[\begin{array} \\0 \\ 1 \\ 1 \\ 0 \end{array}\right] = b + c $$
Notice that $A$ sends the point that was at $a$ to the two vertices adjacent to $a$. That is, if we started at $a$ there is one way to $b$ or $c$ in one step. Notice there is no way to start from $a$ and end at $d$ in one step. The result of applying the matrix to the vector repeatedly essentially records all the possible paths that could be taken starting from some initial vertex.
Lets look at one more application of $A$,
$$ A^2 a = A (Aa) = \left[\begin{array} \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array}\right] \left[ \begin{array} \\ 0 \\ 1 \\ 1 \\ 0 \end{array} \right] = \left[ \begin{array} \\ 2 \\ 0 \\ 0 \\ 2 \end{array} \right] $$
Now we have a vector which represents points located at both $a$ and $d$. This is because they were at $b$ and $c$ and the matrix made them move to the adjacent vertices. Notice that our entries are now $2$'s instead of $1$'s because the points have split twice. These numbers represent the total number of ways to reach a particular vertex after two moves. Generally speaking, all the entries will not have the same numerical values but your graph is very symmetrical.
Hope that helps.
$\endgroup$ 2 $\begingroup$The adjacency matrix of a graph $G=(V,E)$ on $n$ vertices is the $n\times n$ matrix $A$ with $$[A]_{ij}=\begin{cases}1 & ij\in E \\ 0 & ij\notin E \end{cases}$$
$A^m$ denotes the $m$th power of $A$, i.e. $A$ multiplied by itself $m$ times.
One property of this graph is that the number of walks (repeated vertices allowed) of length $r$ from $i$ to $j$ in $G$ is the $i-j$th entry in $A^r$.
$\endgroup$
