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