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