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