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