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