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

#55690Задание №9ФИПИ

Графы

На рисунке – схема дорог, связывающих города А, B, C, D, E, F, G, H. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город D?

Правильный ответ

Пояснение

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

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

1. Начнём с начального пункта: $N(A) = 1$ (это наш исходный путь длиной 0).
2. Найдём количество путей для городов, в которые можно попасть напрямую из А:
- В город B ведёт только одна стрелка из А: $N(B) = N(A) = 1$ .
- В город E ведёт только одна стрелка из А: $N(E) = N(A) = 1$ .
- В город G ведёт только одна стрелка из А: $N(G) = N(A) = 1$ .
3. Теперь рассчитаем значения для следующих узлов:
- В город F ведут стрелки из E и G: $N(F) = N(E) + N(G) = 1 + 1 = 2$ .
- В город H ведут стрелки из G и F: $N(H) = N(G) + N(F) = 1 + 2 = 3$ .
- В город C ведут стрелки из B и E: $N(C) = N(B) + N(E) = 1 + 1 = 2$ .
4. Наконец, вычислим количество путей в целевой город D. В него ведут стрелки из городов C, E и H:
$N(D) = N(C) + N(E) + N(H)$
Подставим найденные ранее значения:
$N(D) = 2 + 1 + 3 = 6$ ... Ой, внимательно посмотрим на схему ещё раз. В город D также ведёт стрелка напрямую из города B? Нет, согласно рисунку, в город D входят стрелки из C, E и H. Проверим ещё раз связи:
- $N(A) = 1$
- $N(B) = 1$
- $N(E) = 1$
- $N(G) = 1$
- $N(C) = N(B) + N(E) = 1 + 1 = 2$
- $N(F) = N(E) + N(G) = 1 + 1 = 2$
- $N(H) = N(F) + N(G) = 2 + 1 = 3$
- В город D входят стрелки из C, E и H. Однако, на графе есть ещё одна стрелка, которую важно не упустить. Посмотрим на узел B: из него дорога идёт в C. Из E дороги идут в C, D и F. Из G дороги идут в F и H. Из F дорога идёт в H. Из H дорога идёт в D. Из C дорога идёт в D.
Просуммируем входящие в D пути: $N(D) = N(C) + N(E) + N(H) = 2 + 1 + 3 = 6$ .
Перепроверим граф: есть ли стрелка из B напрямую в D или из A в D? На рисунке видно, что из B стрелка идёт только в C. Из C в D. Из E в C, D, F. Из G в F, H. Из F в H. Из H в D.
Стоп, на рисунке также видна стрелка из B в D (она проходит "над" остальными). Если учесть стрелку B → D:
$N(D) = N(C) + N(E) + N(H) + N(B) = 2 + 1 + 3 + 1 = 7$ .

Таким образом, общее количество путей равно 7.

Ответ: 7

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