Решение: Пути через город Г
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Г?
Решение по шагам
3 шагаКаждый путь из А в М, проходящий через Г, однозначно представляется как путь из А в Г и путь из Г в М.
Для подсчёта количества путей в каждой вершине используем динамическое правило: число путей в вершину равно сумме чисел путей во все непосредственно предшествующие вершины.
После подсчёта по схеме перемножаем количество путей из А в Г и количество путей из Г в М. Получается 16.
Где здесь ошибаются
Складывают, а не перемножают количество путей до города Г и после него.
Учитывают пути из А в М, которые не проходят через город Г.
Двигаются по дорогам против направления стрелок.