Решение задач типа 11

(К.Поляков) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Решение:

1)      будем обозначать через N_X количество различных путей из города А в город X

2)      для города А есть только один маршрут – никуда не двигаться, поэтому N_A = 1

3)      для любого города X количество маршрутов N_X можно вычислить как

N_x = N_y + … + N_z

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например,

         N_Л = N_И + N_Ж + N_К

4)      около каждого города будем записывать количество маршрутов из А в этот город

5)      начнем считать количество путей с начала маршрута – с города А: 

6)      теперь находим те вершины, в которые можно попасть напрямую из уже рассмотренных вершин (пока – только из А), это Б и Г, для них тоже количество путей равно 1:

7)      теперь можно определить количество путей для В и Е; в В можно приехать только из А, Б и Г, а в Е – только из Г:

         N_В = N_А + N_Б + N_Г = 1 + 1 + 1 = 3

         N_Е = N_Г = 1

8)      теперь можно определить количество путей для Д, Ж и К; в Д можно приехать только из Б и В, в Ж – из В и Е, а в Е – только из Г:

         N_Д = N_Б + N_В = 1 + 3 = 4

         N_Ж = N_В + N_Е = 3 + 1 = 4

         N_К = N_Е­ = 1

9)      теперь можно определить количество путей для И, куда можно приехать только из Д (N_И = N_Д) и, наконец, для Л:

         N_Л = N_Д + N_И + N_Ж + N_К = 13

        

10)   Ответ: 13.