Решение: Количество путей в графе
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?
Схема ориентированных дорог между городами. Саму картинку ещё готовим — у остальных задач темы она на месте.
Решение по шагам
5 шаговВ город A имеется один начальный путь: путь нулевой длины.
$$A=1$$Рассчитаем количество путей до промежуточных городов по направлениям стрелок.
$$B=1,\quad E=1,\quad G=A+E=1+1=2$$Для города C пути приходят из B и E, а для города F — из E и G.
$$C=B+E=1+1=2,\quad F=E+G=1+2=3$$В город H ведут дороги из G и F.
$$H=G+F=2+3=5$$В город D ведут дороги из C, F и H. Складываем количества путей.
$$D=C+F+H=2+3+5=10$$Где здесь ошибаются
Не учитывать все входящие в город D дороги.
Считать пути без учёта направления стрелок.
Складывать города вместо количества путей, ведущих в них.