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