1
$\begingroup$

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

enter image description here

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.

  • 0
    Since you invited correction, I took the liberty of polishing up the English when I added the image.2012-05-23

3 Answers 3

4

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

  • 0
    @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.2012-05-23
3

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

labeled version

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.

  • 0
    Disappearing is common here. We just carry on...2012-05-24
0

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$.