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