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