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