Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.