13
Решение: Пути через заданный город
ЕГЭ · Информатика · Задание 13 · Графы и пути
ПовышеннаяФИПИ4BDB1EКороткий ответ≈ 4 минутыРазбор в 3 шагаОтвет сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Д?
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
3 шага1
Рассмотрим каждый путь из А в М, проходящий через Д, как объединение пути из А в Д и пути из Д в М.
$$N_{А\to М\ через\ Д}=N_{А\to Д}\cdot N_{Д\to М}$$2
Подсчитываем количество направленных путей по схеме, двигаясь от начального города к конечному и складывая количества путей, ведущих в каждую вершину.
Перемножив количество путей из А в Д и из Д в М, получаем искомое число.
$$N_{А\to М\ через\ Д}=12$$Ответ
12
12
так ответ выглядит в бланкеГде здесь ошибаются
Считать пути, не проходящие через город Д.
Учитывать направление дороги наоборот.
Сложить вместо умножения количество путей до города Д и после него.