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