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