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

Решение. Для решения задачи по поиску количества путей в ориентированном графе воспользуемся методом динамического программирования. Мы будем последовательно вычислять количество способов добраться из начального пункта $A$ в каждый следующий пункт, суммируя значения в тех вершинах, из которых ведут стрелки в текущую.

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

1. Начнём с исходной точки:
$N(A) = 1$ (это наш единственный начальный путь).

2. Найдём значения для вершин, в которые можно попасть напрямую из $A$:
$N(B) = N(A) = 1$ (в $B$ ведёт только одна стрелка из $A$).
$N(C) = N(A) = 1$ (в $C$ ведёт только одна стрелка из $A$).
$N(D) = N(A) + N(B) + N(C)$. Подставим уже найденные значения: $N(D) = 1 + 1 + 1 = 3$.

3. Теперь рассчитаем значения для следующих вершин:
$N(E) = N(B) + N(D)$. Подставляем: $N(E) = 1 + 3 = 4$.
$N(F) = N(C) + N(D)$. Подставляем: $N(F) = 1 + 3 = 4$.

4. Наконец, вычислим количество путей до конечного пункта $G$:
В город $G$ ведут дороги из пунктов $E$ и $F$.
$N(G) = N(E) + N(F)$
$N(G) = 4 + 4 = 8$.

Таким образом, существует 8 различных путей из города $A$ в город $G$.

Ответ: 8

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