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