МОШ 2021, 11 класс, задача 4
В некоторой стране есть городов, которые связаны такой сетью дорог, что из любого города в любой другой можно проехать только одним способом без разворотов. Схема сети дорог известна, развилки и перекрестки сети необязательно являются городами, всякая тупиковая ветвь сети обязательно заканчивается городом. Навигатор может измерить длину пути по этой сети между любыми двумя городами. Можно ли за таких измерений гарантированно определить длину всей сети дорог?
(П. А. Бородин)
Решение. Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, развилки и перекрестки, а рёбрами — дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом.
Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее, пусть между некоторыми городами и существует путь, содержащий какую-то вершину цикла. Он обязательно найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль цикла, мы получим еще один путь между и . Значит, циклов в нашем графе быть не может и это действительно дерево.
По условию задачи все концевые вершины дерева — города. Назовем эти города концевыми. Назовем также концевой город следующим за концевым городом , если по пути из в на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь концевой город и померим расстояние между ним и следующим за ним концевым городом . Потом померим расстояние между и следующим за ним концевым городом и так далее. После не более чем таких измерений мы вернемся в исходный город .
Покажем, что при этом каждая дорога нашей сети будет пройдена ровно два раза в противоположных направлениях. Рассмотрим произвольную дорогу. При удалении из дерева любого ребра оно распадается на две компоненты связности и , причем каждая из них содержит города. Пусть изначально мы находились в . Поскольку необходимо обойти все города сети, мы должны пройти по этой дороге два раза: первый раз, когда движемся из в , и второй, когда возвращаемся обратно. Процедура обхода устроена таким образом, что мы посетим все вершины компоненты до того, как покинем её, поэтому больше проходить по дороге из в не потребуется.
Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.