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