13
Решение: Подсчёт путей в графе
ЕГЭ · Информатика · Задание 13 · Графы и пути
ПовышеннаяФИПИ0ACEE4Короткий ответ≈ 3 минутыРазбор в 3 шагаОтвет сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
3 шага1
Обозначим через $N(X)$ количество путей из города А в город $X$. Для начального города $N(А)=1$.
2
Для каждого следующего города используем правило: количество путей в него равно сумме количеств путей в города, из которых в него направлены дороги.
$$N(X)=\sum_{Y\to X}N(Y)$$Последовательно вычисляя значения по схеме дорог от города А к городу М, получаем $N(М)=27$.
Ответ
27
27
так ответ выглядит в бланкеГде здесь ошибаются
Считать дороги вместо различных маршрутов.
Учитывать движение против направления стрелок.
Не складывать пути, приходящие в город из разных предшествующих городов.