Сверь числа и знаки с фото.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? [Рисунок: направленный граф из 9 вершин. Вершина А слева. Далее вершины Б (сверху) и Г (снизу). От А идут стрелки в Б и Г. Из Б и Г стрелки идут в В и Е. Из Г также стрелка в Ж. Из В стрелки в Д и Ж. Из Е стрелки в Д, К и Л. Из Д стрелка в Л. Из Ж стрелки в К и Л. Из К стрелка в Л.]
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? [Рисунок: направленный граф из 7 вершин. Вершина А слева. Далее вершины Б (сверху), В (в центре) и Г (снизу). От А идут стрелки в Б, В и Г. Из Б стрелка в В. Из Г стрелки в В, Д и Е. Из В стрелки в Д, Е и К. Из Д и Е стрелки в К.]
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? [Рисунок: направленный граф из 11 вершин. Вершина А слева. От А стрелки в Б, В, Г. Из Б в В, Е. Из Г в В, З. Из В в Д, Е, З. Из Е в Д, Ж, И. Из Д в Ж, З, И. Из З в Ж, К. Из Ж в И, К, Л. Из И и К стрелки в Л.]
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? [Рисунок: направленный граф из 11 вершин. Вершина А слева. От А стрелки в Б, В, Г. Из Б в В, Е. Из Г в В, З. Из В в Д, Ж, Е. Из Е в Д, Ж, И. Из Д в Ж, З, И. Из З в Ж, К. Из Ж в И, К, Л. Из И и К стрелки в Л.]
На рисунке — схема дорог, связывающих города А, В, С, D, E, G, H, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город D? [Рисунок: направленный граф из 8 вершин. Вершина А слева. От А стрелки в B, H, G. Из B в C, H, E. Из G в H, E, F. Из H в E. Из C в E, D. Из E в D, F. Из F в D.]
Я решил все пять задач на подсчёт путей в графах. В основе решения лежит метод динамического программирования: количество путей в каждый город равно сумме количеств путей во все города, из которых в него ведут стрелки. Для стартового города \(A\) количество путей равно 1.
1. Схема 1 (из \(A\) в \(Л\))
Считаем последовательно:
- \(Б = 1\), \(Г = 1\)
- \(В = 1 (Б) + 1 (Г) = 2\)
- \(Е = 1 (Б) + 1 (Г) = 2\)
- \(Ж = 2 (В) + 1 (Г) = 3\)
- \(Д = 2 (В) + 2 (Е) = 4\)
- \(К = 2 (Е) + 3 (Ж) = 5\)
- \(Л = 4 (Д) + 2 (Е) + 3 (Ж) + 5 (К) = \mathbf{14}\)
Ответ: 14
2. Схема 2 (из \(A\) в \(К\))
- \(Б = 1\), \(Г = 1\)
- \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
- \(Д = 1 (Г) + 3 (В) = 4\)
- \(Е = 1 (Г) + 3 (В) = 4\)
- \(К = 3 (В) + 4 (Д) + 4 (Е) = \mathbf{11}\)
Ответ: 11
3. Схема 3 (из \(A\) в \(Л\))
- \(Б = 1\), \(Г = 1\)
- \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
- \(Е = 1 (Б) + 3 (В) = 4\)
- \(З = 1 (Г) + 3 (В) = 4\)
- \(Д = 3 (В) + 4 (Е) = 7\)
- \(Ж = 7 (Д) + 4 (Е) + 4 (З) = 15\)
- \(И = 7 (Д) + 4 (Е) + 15 (Ж) = 26\)
- \(К = 4 (З) + 15 (Ж) = 19\)
- \(Л = 15 (Ж) + 26 (И) + 19 (К) = \mathbf{60}\)
Ответ: 60
4. Схема 4 (из \(A\) в \(Л\))
Здесь есть дополнительная дорога из \(В\) в \(Ж\) по сравнению с предыдущей схемой.
- \(Б = 1\), \(Г = 1\)
- \(В = 1 (А) + 1 (Б) + 1 (Г) = 3\)
- \(Е = 1 (Б) + 3 (В) = 4\)
- \(З = 1 (Г) + 3 (В) = 4\)
- \(Д = 3 (В) + 4 (Е) = 7\)
- \(Ж = 3 (В) + 7 (Д) + 4 (Е) + 4 (З) = 18\)
- \(И = 7 (Д) + 4 (Е) + 18 (Ж) = 29\)
- \(К = 4 (З) + 18 (Ж) = 22\)
- \(Л = 18 (Ж) + 29 (И) + 22 (К) = \mathbf{69}\)
Ответ: 69
5. Схема 5 (из \(A\) в \(D\))
- \(B = 1\), \(G = 1\)
- \(H = 1 (A) + 1 (B) + 1 (G) = 3\)
- \(C = 1 (B) = 1\)
- \(E = 1 (B) + 1 (G) + 3 (H) + 1 (C) = 6\)
- \(F = 1 (G) + 6 (E) = 7\)
- \(D = 1 (C) + 6 (E) + 7 (F) = \mathbf{14}\)
Ответ: 14
Главный принцип: всегда записывай для каждого города сумму путей тех городов, от которых к нему идут стрелки, и двигайся слева направо.