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