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