9
Решение: Количество путей в графе
ОГЭ · Информатика · Задание 9 · Графы и пути
ПовышеннаяФИПИ2D3359Короткий ответ≈ 5 минутРазбор в 4 шагаОтвет сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
4 шага1
Последовательно вычислим количество путей из города А в каждую вершину графа.
$$N_{Б}=1,\quad N_{В}=N_{А}+N_{Б}=2,\quad N_{Г}=N_{А}+N_{В}=3,\quad N_{Д}=1$$2
Для следующих вершин получаем:
$$N_{Е}=N_{Б}+N_{В}=3,\quad N_{Ж}=N_{Г}+N_{Д}=4,\quad N_{И}=N_{Е}=3$$3
Количество путей в город З складывается из путей через Е и Ж, а в К ведёт только путь через Ж.
$$N_{З}=N_{Е}+N_{Ж}=7,\quad N_{К}=N_{Ж}=4$$В город Л можно попасть из городов Е, З, И и К. Складываем количества путей из города А в эти вершины.
$$N_{Л}=N_{Е}+N_{З}+N_{И}+N_{К}=3+7+3+4=17$$Ответ
17
17
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают один из входящих в город Л маршрутов.
Считают дороги вместо различных путей.
Повторно считают один и тот же путь при переходе через несколько вершин.