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