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