9
Шешімі: Количество путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИ4BB802Қысқа жауап≈ 3 минутТалдау 4 қадамЖауап сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешімін қадамдап көрсету
4 қадам1
Запишем количество путей из А к промежуточным вершинам. В города Б и Д ведёт по одному пути, а в город В — два пути: непосредственно из А и через Б.
$$N_{Б}=1,\quad N_{Д}=1,\quad N_{В}=2$$2
В город Г ведут дороги из А, В и Д, поэтому количество путей в него равно четырём.
$$N_{Г}=1+2+1=4$$3
В город Е ведут дороги из Б и В, а в город Ж — из Д и Г.
$$N_{Е}=1+2=3,\quad N_{Ж}=1+4=5$$В город К ведут дороги из Е, Г и Ж. Складываем количества путей.
$$N_{К}=3+4+5=12$$Жауап
12
12
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывать пути, проходящие через промежуточные вершины.
Двигаться по дороге против направления стрелки.
Считать разные маршруты одинаковыми.