Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение по шагам
5 шаговОбозначим через $N_X$ количество путей из города А в город $X$. Для начальной вершины $N_{\text{А}}=1$.
Последовательно подсчитываем количество путей до промежуточных городов: $N_{\text{Б}}=1$, $N_{\text{В}}=2$, $N_{\text{Г}}=3$, $N_{\text{Д}}=1$, $N_{\text{Е}}=3$, $N_{\text{Ж}}=4$.
Для города З складываем количества путей из всех вершин, ведущих в З: из В, Г, Е и Ж.
$$N_{\text{З}}=2+3+3+4=12$$В город И ведут пути из Е, а в город К — из Ж.
$$N_{\text{И}}=3,\quad N_{\text{К}}=4$$В город Л ведут дороги из З, И и К, поэтому складываем количества путей до этих городов.
$$N_{\text{Л}}=12+3+4=19$$Где здесь ошибаются
Не учитывать направление стрелок.
Посчитать только непосредственные дороги в город Л, не учитывая пути до городов З, И и К.
Повторно считать один и тот же путь.