9
Шешімі: Количество путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИ5B1431Қысқа жауап≈ 3 минутТалдау 4 қадамЖауап сверен с ключом
Условие
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город G?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешімін қадамдап көрсету
4 қадам1
Из города A в города B и C ведёт по одному пути.
$$N_B = 1,\quad N_C = 1$$2
В город D можно попасть только из B, а в город E — из B и C.
$$N_D = N_B = 1,\quad N_E = N_B + N_C = 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 = 1 + 2 + 3 = 6$$Жауап
6
6
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывать путь через город F.
Считать города, а не различные маршруты.
Не складывать пути, ведущие в G из всех трёх соседних вершин.