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