Сколько существует различных путей из города А в город М, проходящих через город В?
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В?
Решение:
Определяем количество путей из города А в город В:
— напрямую из А в В,
— через Б (АБВ),
— через Г , (Из А в Г можно попасть напрямую(АГ) и через Д (АДГ), получается, из города А в город В через Г можно попасть 2мя способами — (АГВ) и (АДГВ).
итого: 4
Теперь будем определять пути из пункта В в пункт М.
В пункт Е ведут 4 маршрута из В.
В пункт Ж ведут 8 маршрутов: 4 маршрута из В, 4 маршрута из Е.
В пункт И ведут 12 маршрутов: 4 маршрута из Е, 8 маршрутов из Ж.
В пункт К ведут 12 маршрутов из И.
В пункт Л ведут 12 маршрутов из И.
В город М ведут 36 маршрутов: 12 маршрутов из И, 12 маршрутов из К, 12 маршрутов из Л.
Ответ: 36
