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