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