Начнем считать количество путей с конца маршрута – с города Л. N_X — количество различных путей из города А в город X, N — общее число путей.

В "Л" можно приехать из И, Д, Е, Ж или К, поэтому N = N_Л = N_И + N _Д + N _Е + N _Ж + N _К (*)

Аналогично:

N_И = N_Д = 4;

N_Д = N_Б + N_Е = 1 + 3 = 4;

N_Е = N_В = 3;

N_Ж = N_Е + N_В + N_Г = 3 + 3 + 1 = 7;

N_К = N_Ж = 7.

Добавим еще вершины:

N_Б = N _А = 1;

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

N_Г = N_А = 1.

Подставим в формулу (*):

N = N_Л = 4 + 4 + 3 + 7 + 7 = 25.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

Е = Д = 3 (В и Г не учитываем, поскольку путь должен проходить через город Д).

Ж = Д + Е = 6.

И = Е = 3.

К = Ж + И = 9.

Л = К = М = 9.

Н = Л + М = 18.

Примечание. Необходимо найти количество различных путей из города А в город Н, проходящих через город Д.

Начнем считать количество путей с конца маршрута – с города И. N_X — количество различных путей из города А в город X, N — общее число путей.

В "И" можно приехать из Д, Ж, или З, поэтому N = N_И = N_Д + N_Ж + N _З (1)

Аналогично:

N_Д = N_Б;

N_Ж = N_Б + N_В + N_Е;

N_З = N_Ж.

Добавим еще вершины:

N_Б = N_А = 1;

N_В = N_А + N_Г = 1 + 1 = 2;

N_Е = N_В = 2;

N_Г = N_А = 1;

Преобразуем первые вершины с учетом значений вторых:

N_Д = N_Б = 1;

N_Ж = N_Б + N_В + N_Е = 1 + 2 + 2 = 5;

N_З = N_Ж = 5.

Подставим в формулу (1):

N = N_К = 1 + 5 + 5 = 11.

Начнем считать количество путей с конца маршрута – с города И. N_X — количество различных путей из города А в город X, N — общее число путей.

В "И" можно приехать из Д, Ж, или З, поэтому N = N_И = N_Д + N_Ж + N _З (1)

Аналогично:

N_Д = N_Б;

N_Ж = N_Б + N_В + N_Е;

N_З = N_Ж.

Добавим еще вершины:

N_Б = N_А = 1;

N_В = N_А + N_Г = 1 + 1 = 2;

N_Е = N_В = 2;

N_Г = N_А = 1;

Преобразуем первые вершины с учетом значений вторых:

N_Д = N_Б = 1;

N_Ж = N_Б + N_В + N_Е = 1 + 2 + 2 = 5;

N_З = N_Ж = 5.

Подставим в формулу (1):

N = N_К = 1 + 5 + 5 = 11.

Начнем считать количество путей с конца маршрута – с города М. N_X — количество различных путей из города А в город X, N — общее число путей.

В "М" можно приехать из Д, Е, К или Л, поэтому N = N_М = N_Д + N_Е + N _К + N _Л (1)

Аналогично:

N_Д = N_Г;

N_Е = N_Г + N_Ж + N_К;

N_К = N_И,

N_Л = N_К.

Добавим еще вершины:

N_Г = N_В + N_Ж;

N_Ж = N_В + N_И;

N_И = N_А = 1;

N_В = N_Б + N_А = 2;

N_Б = N_А = 1.

Преобразуем вершины:

N_Г = N_В + N_Ж = 2 + 3 = 5;

N_Ж = N_В + N_И = 2 + 1 = 3;

N_И = N_А = 1;

N_В = N_Б = 1;

N_Б = N_А = 1.

N_Д = N_Г = 5;

N_Е = N_Г + N_Ж + N_К = 5 + 3 + 1 = 9;

N_К = N_И = 1,

N_Л = N_К = 1.

Подставим в формулу (1):

N = N_М = 5 + 9 + 1 + 1 = 16.

Начнем считать количество путей с конца маршрута – с города E. N_X — количество различных путей из города А в город X, N — общее число путей.

В "Е" можно приехать из В, Е, или G, поэтому N = N_E = N_B + N_A + N _G(1)

Аналогично:

N_B = N_A = 1;

N_A = 1;

N_G = N_A + N_K = 2;

Подставим в формулу (1):

N = N_К = 1 + 1 + 2 = 4.

Начнем считать количество путей с конца маршрута – с города Л. N_X — количество различных путей из города А в город X, N — общее число путей.

В "Л" можно приехать из И, Е, Ж или К, поэтому N = N_Л = N_И + N _Е + N _Ж + N _К (*)

Аналогично:

N_И = N_Д + N_Е = 3 + 4 = 7;

N_Е = N_Д + N_В = 3 + 1 = 4;

N_Ж = N_В + N _Г = 1 + 2 = 3;

N_К = N_Ж = 3.

Добавим еще вершины:

N_Д = N_Б + N _В = 2 + 1 = 3;

N_В = N_А = 1;

N_Г = N_А + N _В = 1 + 1 = 2;

N_Б = N _А + N _В = 1 + 1 = 2.

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б = 1 + 1 = 2

Е = А + Б + В + Г + Д= 1 + 1 + 2 + 2 + 1 = 7

К = Е = 7

Л = Е + Д = 7 + 1 = 8

М = Е + Л + К = 7 + 8 + 7 = 22

Н = М + К + Л = 22 + 7 + 8 = 37

П = Н = 37

Р = Н + П = 37 + 37 =74

Т = Р + П = 74 + 37 = 111

Начнем считать количество путей с конца маршрута – с города М. N_X — количество различных путей из города А в город X, N — общее число путей.

В "М" можно приехать из K, H или L, поэтому N = N_M = N_K + N_H + N _L (1)

Аналогично:

N_K = N_H;

N_H = N_F + N_B + N_C + N_D + N_G + N_E;

N_L = N_H.

Добавим еще вершины:

N_F = N_B = 2;

N_B = N_A + N_C = 2;

N_C = N_A = 1;

N_D = N_A + N_C = 2;

N_E = N_D + N_A = 2 + 1 = 3;

N_G = N_E = 3.

Тогда:

N_H = 2 + 2 + 1 + 2 + 3 + 3 = 13;

N_K = 13;

N_L = 13.

Подставим в формулу (1): N = 3 · N_H = 3 · 13 = 39.

Количество путей до города Х = количеству путей добраться в любой из тех городов, из которых есть дорога в Х.

С помощью этого наблюдения подсчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б = 1 + 1 = 2

Е = А + Б + В + Г + Д= 1 + 1 + 2 + 2 + 1 = 7

К = Е + Б = 7 + 1 =8

Л = Е = 7

М = Л + К = 8 + 7 = 15

Н = М + К + Л = 15 + 7 + 8 = 30

П = Н = Р = 30

Т = Р + П + Н = 30+ 30 + 30 = 90

Начнем считать количество путей с конца маршрута – с города К. N_X — количество различных путей из города А в город X, N — общее число путей.

В "К" можно приехать из И, Ж, или З, поэтому N = N_К = N_И + N_Ж + N _З (1)

Аналогично:

N_И = N_Д;

N_Ж = N_Д + N_В + N_Е;

N_З = N_Е.

Добавим еще вершины:

N_Д = N_Б + N_В ;

N_В = N_Б + N_Г;

N_Е = N_В + N_Г ;

N_Г = N_А = 1;

N_Б = N_А = 1.

Преобразуем вершины:

N_Д = N_Б + N_В = 1 + 2 = 3;

N_В = N_Б + N_Г = 1 + 1 = 2;

N_Е = N_В + N_Г = 2 + 1 = 3;

N_Г = N_А = 1;

N_Б = N_А = 1.

N_И = N_Д = 3;

N_Ж = N_Д + N_В + N_Е = 3 + 2 + 3 = 8;

N_З = N_Е = 3.

Подставим в формулу (1):

N = N_К = 3 + 8 + 3 = 14.