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