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