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.

Possible Duplicate:
Graph-theory exercise

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

marked as duplicate by lhf, Phira, tomasz, Jennifer Dylan, Matt N. Aug 25 '12 at 21:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
Your English is quite understandable - but I couldn't help you with uploading the picture. Are you sure this is a working link? –  Ilya May 28 '12 at 8:15
    
Где З? ;-)$\quad$ –  Brian M. Scott May 28 '12 at 8:20
    
@Ilya: Extra blank space after ‘http://’ $-$ never mind, I see that someone got it. –  Brian M. Scott May 28 '12 at 8:22
    
You can try to work backwards from city K. –  Raskolnikov May 28 '12 at 8:26

2 Answers 2

It’s like the earlier problem. Work backwards from К: the only way to get there directly is from Е. Е can only be reached directly from В and Г. Г can be reached only from А, while В can be reached from Б or А, and Б can be reached only from А. If you backtrack from К to А, the first step must be to Е. After that you have two choices, В and Г. If you go to В, you have three choices: directly to А, Б to А, or Г to А. Thus, there are three routes back through В. If you go instead to Г, you have no further choices: you can only go to А. Thus, there are altogether four routes:

$$\begin{align*} &\text{А}\rightarrow\text{Г}\rightarrow\text{Е}\rightarrow\text{К}\\ &\text{А}\rightarrow\text{В}\rightarrow\text{Е}\rightarrow\text{К}\\ &\text{А}\rightarrow\text{Б}\rightarrow\text{В}\rightarrow\text{Е}\rightarrow\text{К}\\ &\text{А}\rightarrow\text{Г}\rightarrow\text{В}\rightarrow\text{Е}\rightarrow\text{К} \end{align*}$$

When you trace back, you see that only part of the graph actually matters:

                 Б  
                / \  
               /   \  
              А-----В  
               \   / \  
                \ /   \  
                 Г-----Е-----К

(All arrows here are understood to point from left to right.)

share|improve this answer
    
How many ways are there,tell me please? –  skeeph May 28 '12 at 8:57
    
@skeeph: I did: there are three. –  Brian M. Scott May 28 '12 at 8:59
    
Are you sure? This is very important for me –  skeeph May 28 '12 at 9:05
    
And $\text{А}\rightarrow\text{Г}\rightarrow\text{B}\rightarrow\text{Е}\rightarrow\te‌​xt{К}\\$ too, so 4 path. This question is exactly equal to the earlier one, just check the other suggested solution: topological sort + go backward keeping the number of possible solution starting in a point, with the recursion $N(A) =$ sum over A childs –  carlop May 28 '12 at 9:08
    
@skeeph: Sorry, skeeph: I was working from memory and accidentally miscounted. It should be four ways. –  Brian M. Scott May 28 '12 at 9:12

Assume that the graph is acyclic.

Let $P(v)$ be the predecessors of $v$ (i.e. $P(v) = \{u : (u, v) \in V\}$).

Let $n_u(v)$ be the number of ways of reaching $v$ from $u$, where we define $n_u(u) = 1$.

Then, assuming no duplicate edges, $$n_u(v) = \sum_{w\in P(v)} n_u(w)$$

This is easily proven by induction over a topological sort of the vertices.

share|improve this answer

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