Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Схема направленных дорог между городами. Саму картинку ещё готовим — у остальных задач темы она на месте.
Решение по шагам
3 шагаПрисвоим городу А значение 1: это единственный пустой путь, начинающийся в А.
$$N(А)=1$$Для каждой следующей вершины вычисляем количество путей как сумму значений всех вершин, из которых в неё входят стрелки.
Последовательно выполняя такие сложения по направлению стрелок, получаем для конечной вершины Л сумму 27.
Где здесь ошибаются
Учитывают дороги без учёта направления стрелок.
Считают отдельные дороги вместо полных путей от А до Л.
Пропускают один из вариантов прохождения через промежуточные города.