Деревья и остовные деревья

Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, развилки и перекрестки, а ребрами — дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом. Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее, пусть между некоторыми городами и существует путь, содержащий какую-то вершину цикла. Он обязательно найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль цикла, мы получим еще один путь между и Значит, циклов в нашем графе быть не может и это действительно дерево.

По условию задачи все концевые вершины дерева — города. Назовем эти города концевыми. Назовем также концевой город следующим за концевым городом если по пути из в на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь концевой город и измерим расстояние между ним и следующим за ним концевым городом Потом измерим расстояние между и следующим за ним концевым городом и так далее. После не более чем таких измерений мы вернемся в исходный город

Покажем, что при этом каждая дорога нашей сети будет пройдена ровно два раза в противоположных направлениях. Рассмотрим произвольную дорогу. При удалении из дерева любого ребра оно распадается на две компоненты связности и причем каждая из них содержит города. Пусть изначально мы находились в Поскольку необходимо обойти все города сети, мы должны пройти по этой дороге два раза: первый раз — когда движемся из в а второй — когда возвращаемся обратно. Процедура обхода устроена таким образом, что мы посетим все вершины компоненты до того, как покинем ее, поэтому больше проходить по дороге из в не потребуется.

Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.