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