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