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