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