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