9
Шешімі: Подсчёт путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИ33203DҚысқа жауап≈ 3 минутТалдау 2 қадамЖауап сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешімін қадамдап көрсету
2 қадам1
Из города А начинаются пути через города Б, В и Г. Перечислим все маршруты, которые заканчиваются в городе К.
После учёта направлений стрелок и исключения повторных маршрутов получаем шесть различных путей из А в К.
Жауап
6
6
так ответ выглядит в бланкеГде здесь ошибаются
Учитывать движение по дороге в направлении, противоположном стрелке.
Посчитать один и тот же путь несколько раз.
Принять промежуточную вершину за конечную.