4
$\begingroup$

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.

  • 0
    You$ $can try to work backwards from city K.2012-05-28

2 Answers 2

3

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

  • 0
    @skeeph: I gave a complete solution. What part of it do you not understand?2012-05-28
0

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.