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