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