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

Для решения задач на подсчет количества путей в ориентированном графе, будем двигаться от начального пункта (А) к конечному, последовательно вычисляя количество путей в каждую вершину. Количество путей в вершину равно сумме количеств путей во все вершины, из которых идут стрелки в данную точку. ### Решение задачи 60 Пусть $N(X)$ — количество путей из А в город X. 1. $N(A) = 1$ 2. Из А ведут пути в Г, Б, В: $N(Г) = N(A) = 1$ $N(Б) = N(A) = 1$ $N(В) = N(A) = 1$ 3. В Б входят стрелки из А и Г: $N(Б) = N(A) + N(Г) = 1 + 1 = 2$ 4. В В входят стрелки из А, Г, Б: $N(В) = N(A) + N(Г) + N(Б) = 1 + 1 + 2 = 4$ 5. В Е входят стрелки из Г: $N(Е) = N(Г) = 1$ 6. В Д входят стрелки из Б: $N(Д) = N(Б) = 2$ 7. В Ж входят стрелки из В, Е: $N(Ж) = N(В) + N(Е) = 4 + 1 = 5$ 8. В И входят стрелки из Д: $N(И) = N(Д) = 2$ 9. В К входят стрелки из Е, Ж, И: $N(К) = N(Е) + N(Ж) + N(И) = 1 + 5 + 2 = 8$ **Ответ: 8.** ### Решение задачи 61 Пусть $N(X)$ — количество путей из А в город X. 1. $N(A) = 1$ 2. В Б входят стрелки из А: $N(Б) = N(A) = 1$ 3. В В входят стрелки из А: $N(В) = N(A) = 1$ 4. В Г входят стрелки из А, Б, В: $N(Г) = N(A) + N(Б) + N(В) = 1 + 1 + 1 = 3$ 5. В Е входят стрелки из В: $N(Е) = N(В) = 1$ 6. В Д входят стрелки из Б: $N(Д) = N(Б) = 1$ 7. В Ж входят стрелки из Г, Е, Д: $N(Ж) = N(Г) + N(Е) + N(Д) = 3 + 1 + 1 = 5$ **Ответ: 5.**