Шешімі: Пути через город Л
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л?
Шешім по шагам
2 қадамРассматриваем только пути, проходящие через город Л. Каждый такой путь однозначно разбивается на путь из А в Л и путь из Л в М.
$$N_{А\to М\ через\ Л}=N_{А\to Л}\cdot N_{Л\to М}$$Для ориентированной схемы дорог последовательно подсчитываем число путей до вершин, складывая количества путей до всех их непосредственных предшественников. По рисунку произведение числа путей из А в Л и из Л в М равно 20.
$$N_{А\to Л}\cdot N_{Л\to М}=20$$Где здесь ошибаются
Подсчитывают все пути из А в М, не исключая пути, которые не проходят через Л.
Складывают вместо умножения число путей до Л и число путей от Л до М.
Учитывают дороги как двусторонние, хотя движение разрешено только по стрелкам.