Какую наименьшую длину может иметь маршрут, если нужно пройти по каждой улице этого города и вернуться в прежнее место? (По каждой улице можно проходить любое число раз.)
Оценка. Аналогично решению задачи 197840 доказываем, что длина маршрута не меньше 60 + 16 : 2 = 68.
Доказательство возможности обхода. "Раздвоим" 8 улиц (см. рисунок). Теперь в графе 68 рёбер, и все его вершины чётны. Согласно решению задачи 130806 в нём есть эйлеров цикл.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
