Possible Duplicate:
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.

-

## marked as duplicate by lhf, Phira, tomasz, Jennifer Dylan, Rudy the ReindeerAug 25 '12 at 21:26

Где З? ;-)$\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

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

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

-