Решение: Количество путей в графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение по шагам
3 шагаРассмотрим схему как ориентированный граф. Для каждого города определяем число путей из города А, двигаясь по стрелкам.
В городе А имеется один начальный путь: путь нулевой длины. Для каждого следующего города складываем количества путей в его непосредственных предшественников.
После последовательного подсчёта по всей схеме количество путей, ведущих в город Л, равно 16.
$$N(Л)=16$$Где здесь ошибаются
Считать дороги вместо различных маршрутов.
Учитывать движение против направления стрелок.
Не складывать пути, приходящие в один и тот же город из разных предшественников.