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