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