Шешімі: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Шешім по шагам
4 қадамОбозначим через $N_X$ количество путей из А в вершину $X$. Для начальной вершины $А$ имеем $N_A=1$. По схеме $N_Б=1$, поэтому $N_В=N_A+N_Б=2$.
Рассчитаем количества путей в остальных вершинах: $N_Г=N_A+N_В+N_Д=1+2+1=4$, $N_Е=N_Б+N_В=1+2=3$, $N_Ж=N_Д=1$.
Для вершины З получаем $N_З=N_В+N_Г+N_Е+N_Ж=2+4+3+1=10$. Также $N_И=N_Е=3$ и $N_К=N_Ж=1$.
В город Л ведут дороги из З, И, Ж и К, поэтому $N_Л=N_З+N_И+N_Ж+N_К=10+3+1+1=15$.
Где здесь ошибаются
Не учитывать все входящие в вершину дороги.
Считать пути, проходящие через одну и ту же последовательность вершин, одинаковыми.
Забыть, что в город Л ведут дороги сразу из төрт вершин.