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