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