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