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.