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