Задание №9 — Теоретические основы информатики

Решение. Для решения этой задачи мы воспользуемся методом динамического подсчёта путей. Суть метода заключается в том, что количество путей в конкретный город равно сумме количеств путей во все города, из которых в него ведут прямые дороги.

Обозначим через $N(X)$ количество различных путей из города А в город X.

Шаг 1. Начальная точка.
Для города А, который является началом маршрута, принимаем:
$N(A) = 1$.

Шаг 2. Подсчёт для промежуточных городов.
Будем двигаться последовательно от начала графа к его концу, выбирая те вершины, для которых уже известны значения всех входящих в них стрелок.
1. В город Б ведёт только одна дорога из А:
$N(Б) = N(A) = 1$.
2. В город Г ведёт только одна дорога из А:
$N(Г) = N(A) = 1$.
3. В город В ведут дороги из Б, А и Г. Сложим их значения:
$N(В) = N(Б) + N(A) + N(Г) = 1 + 1 + 1 = 3$.
4. В город Д ведёт только одна дорога из Г:
$N(Д) = N(Г) = 1$.
5. В город Е ведёт только одна дорога из Д:
$N(Е) = N(Д) = 1$.

Шаг 3. Финальный расчёт.
Теперь найдём количество путей в конечный пункт — город К. В него ведут дороги из городов В, Г и Е:
$N(К) = N(В) + N(Г) + N(Е)$
Подставим найденные ранее значения:
$N(К) = 3 + 1 + 1 = 5$.
Внимание: перепроверим схему дорог. В город К ведут стрелки из В, Г и Е. Однако, согласно графу, из города Г дорога идёт также в Д, а из Д в Е. Проверим ещё раз входящие пути в К:
На рисунке видно, что в К входят стрелки из В, Г и Е.
$N(К) = 3 (из В) + 1 (из Г) + 2 (из Е, так как в Е ведут пути через Д и напрямую из Г)$.
Посмотрим внимательнее на узел Е: в него входит стрелка из Д и стрелка из Г.
$N(Е) = N(Д) + N(Г) = 1 + 1 = 2$.
Тогда итоговый расчёт для К:
$N(К) = N(В) + N(Г) + N(Е) = 3 + 1 + 2 = 6$.

Таким образом, существует 6 различных путей из города А в город К.

Ответ: 6

Источник: ФИПИ