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