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.

  • 1
    Your English is quite understandable - but I couldn't help you with uploading the picture. Are you sure this is a working link?2012-05-28
  • 0
    Где З? ;-)$\quad$2012-05-28
  • 0
    @Ilya: Extra blank space after ‘http://’ $-$ never mind, I see that someone got it.2012-05-28
  • 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
    How many ways are there,tell me please?2012-05-28
  • 0
    @skeeph: I did: there are three.2012-05-28
  • 0
    Are you sure? This is very important for me2012-05-28
  • 0
    And $\text{А}\rightarrow\text{Г}\rightarrow\text{B}\rightarrow\text{Е}\rightarrow\text{К}\\$ 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 childs2012-05-28
  • 0
    @skeeph: Sorry, skeeph: I was working from memory and accidentally miscounted. It should be four ways.2012-05-28
  • 0
    @carlop: I didn’t feel like tracking down the earlier problem to see how close they were. The miscount was the result of typing without having the picture in front of me.2012-05-28
  • 0
    My apologies, I was trying to say that @skeeph can have learnt from his previous answer, trying to understand how to calculate the solution for the general problem, istead of posting a different question for an almost equal problem.2012-05-28
  • 0
    @carlop: No apologies needed!2012-05-28
  • 0
    At this moment a have a disadvantage of time, and it is very important to solve this. Please, help me2012-05-28
  • 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.