Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город F?
Схема ориентированных дорог между городами. Саму картинку ещё готовим — у остальных задач темы она на месте.
Решение по шагам
6 шаговСчитаем начальную вершину A источником: в неё ведёт один начальный путь, поэтому $N_A=1$.
$$N_A=1$$В вершины B, C и D ведут пути непосредственно из A, поэтому $N_B=N_C=N_D=1$.
В вершину E ведут дороги из A и D. Следовательно, $N_E=N_A+N_D=1+1=2$.
В вершину G ведут дороги из C и E. Следовательно, $N_G=N_C+N_E=1+2=3$.
В вершину H ведут дороги из E и G. Следовательно, $N_H=N_E+N_G=2+3=5$.
В вершину F ведут дороги из B, G и H. Поэтому общее число путей равно $N_F=N_B+N_G+N_H=1+3+5=9$.
Где здесь ошибаются
Учитывают дороги, направленные из F, хотя путь должен заканчиваться в F.
Считают отдельные дороги вместо различных полных путей.
Пропускают пути, проходящие через вершины E, G и H.