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