# Graph-theory exercise

The picture below shows a graph connecting the cities А, Б, В, Г, Д, Е, Ж, И, К.

On each path you can only move only in direction of the arrow. How many different ways are there from city A to city K?

I understood that this exercise is from graph theory. Please tell me how I can solve exercises like this.

P.S. Sorry for my poor English. It isn't my native language. I would be very grateful if you would mention errors in my English.

-
Since you invited correction, I took the liberty of polishing up the English when I added the image. – Brian M. Scott May 23 '12 at 11:32
Thanks for correcting my errors. – skeeph May 23 '12 at 11:57

Work backwards from К to А. There is only one way to reach К from И. This gives you two ways to reach К from Д. Continue like that.

-
This way take away a lot if time, which I have not much. Isn't there any formulae,etc. for solve it – skeeph May 23 '12 at 12:01
@skeeph, it does not take a lot of time. There is no guessing, just attach the correct numbers to each vertex and the number for a given vertex is the sum of the numbers of the vertices that are directly reachable from it. – lhf May 23 '12 at 12:11

This answer is nothing more than a clarification to lhf's answer. Label the vertices as follows:

Continue backwards as I've done with the first few. For each vertex, follow all the forward arrows one step, and add up the numbers at each end.

-
Thanks for the clarification! – lhf May 23 '12 at 12:37
The next vertex to label is В because all edges from it lead to labeled vertices. – lhf May 23 '12 at 12:38
I guess this must have been a homework problem with a very close deadline, for the op to just disappear like that (and of course based on the above comment). – Dustan Levenstein May 24 '12 at 17:07
Disappearing is common here. We just carry on... – lhf May 24 '12 at 18:39

The adjacency matrix of this graph can be written: $$A:=\left(\begin{array}{ccccccccc} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}\right)$$ where the first index represents the leftmost vertex (call this $1$), and the last index represents the rightmost vertex (call this $8$).

The number of walks from $A$ to $K$ in $k$ steps is $A^k(1,8)$ (the entry in cell $(1,8)$ of $A^k$). Hence the total number of walks from $A$ to $K$ is $$\sum_{k \geq 0} A^k(1,8).$$

In this case, $A^6$ is the all-zero matrix (and consequently $A^k$ for $k \geq 6$ is the all-zero matrix), so the total number of walks from $A$ to $K$ is $$\sum_{0 \leq k \leq 5} A^k(1,8).$$ We can compute this on the computer as $13$.

-