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