9
Решение: Количество путей в графе
ОГЭ · Информатика · Задание 9 · Графы и пути
ПовышеннаяФИПИ42D3BFКороткий ответ≈ 3 минутыРазбор в 4 шагаОтвет сверен с ключом
Условие
На рисунке — схема дорог, связывающих пункты A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта A в пункт H?
Иллюстрация к условию
Открыть задачу и решить самомуСхема ориентированного графа дорог. Саму картинку ещё готовим — у остальных задач темы она на месте.
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
4 шага1
Из A непосредственно выходят пути в C, B и D. Поэтому число путей в C и B равно 1, а в D — 3: из A, через C и через B.
$$N_C=1,\quad N_B=1,\quad N_D=1+1+1=3$$2
В E можно попасть только из C, поэтому число путей в E равно 1. В F ведут пути из B и D.
$$N_E=1,\quad N_F=N_B+N_D=1+3=4$$3
В G ведут пути из D, E и F.
$$N_G=N_D+N_E+N_F=3+1+4=8$$В H можно попасть из E или из G.
$$N_H=N_E+N_G=1+8=9$$Ответ
9
9
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают пути, проходящие через несколько промежуточных вершин.
Считают дороги, а не различные маршруты.
Игнорируют направление стрелок.