13
Шешімі: Пути через город Д
ЕГЭ · Информатика · Тапсырма 13 · Графы и пути
КүрделіФИПИ6CF147Қысқа жауап≈ 3 минутТалдау 3 қадамЖауап сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Д?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
3 қадам1
Каждый путь из А в М, проходящий через Д, однозначно представляется как путь из А в Д и путь из Д в М.
2
По схеме дорог подсчитываем количество направленных путей на каждом участке графа. Произведение количества путей из А в Д и из Д в М даёт общее число путей через Д.
Для данной схемы это количество равно 18.
$$N_{А\to М\text{ через }Д}=N_{А\to Д}\cdot N_{Д\to М}=18$$Жауап
18
18
так ответ выглядит в бланкеГде здесь ошибаются
Считать пути, которые не проходят через город Д.
Учитывать движение по дороге в направлении, противоположном стрелке.
Сложить, а не перемножить количество путей до города Д и после него.