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