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