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