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