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