На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город П, проходящих через город М?

Для решения задачи найдем количество путей, проходящих через город М. Это произведение количества путей из А в М и количества путей из М в П. 1. Найдем количество путей из А в М: - А = 1 - Б = А = 1 - Г = А + Б = 1 + 1 = 2 - Д = А = 1 - В = Б = 1 - Е = Г + Д = 2 + 1 = 3 - Ж = В + Г + Е = 1 + 2 + 3 = 6 - К = В + Ж = 1 + 6 = 7 - Л = К + Ж = 7 + 6 = 13 - М = Ж + Л = 6 + 13 = 19 Количество путей из А в М равно 19. 2. Найдем количество путей из М в П: - М = 1 (начальная точка пути из М) - Л = М = 1 - Н = М = 1 - П = Л + К (в П ведут стрелки из Л и К, но нам нужны только пути из М, значит считаем только от М. Из М в П ведут пути через Л и напрямую из М нельзя, но из М ведет стрелка в Н, а из Н ничего не идет в П, зато из М идет стрелка в Л. Посмотрим на граф внимательнее: из М идет стрелка в Л, и из М идет стрелка в Н. Из Л идет стрелка в П. Значит, из М путь идет только через Л в П. Также есть еще путь М-П? Нет. Путь М-Л-П - это 1 путь). Пересчитаем пути из М в П внимательно: Из М идут стрелки в Л и Н. Из Н стрелок в П нет. Из Л идет стрелка в П. Значит путь один: М -> Л -> П. Количество путей из А в П через М = (пути из А в М) * (пути из М в П) = 19 * 1 = 19. **Ответ: 19**