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