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