|
|
 |
Условие
В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам. В этом графе между каждыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (дерево). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (висячие вершины) – пусть это вершины A1, A2, ..., A100.
Для каждой пары висячих вершин Ai и Aj существует единственный путь между ними, назовём количество рёбер на этом пути расстоянием между этими вершинами и будем обозначать через d(Ai, Aj).
Из конечности числа способов разбить эти 100 вершин на 50 пар следует,
что при одном из способов достигается максимум суммы расстояний между вершинами
в парах. Соединим пары вершин при этом разбиении 50 новыми рёбрами
(остальные рёбра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа.
Предположим противное, пусть при удалении ребра между вершинами B и C граф распался на две компоненты. Ясно, что удалённое ребро было старым, а вершины B и C принадлежат разным компонентам. В каждой части должна быть вершина, из которой выходит ровно одно старое ребро, а каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины Ai и Aj, а в другой – соединяющее вершины Ak и Am. Пути l и L, соединяющие соотвественно Ai с Ak и Aj с Am, должны содержать ребро BC. Следовательно, путь из Ai в Aj состоит из участка пути l, соединяющего Ai с B, и участка пути L, соединяющего B с Aj. Аналогично путь из Ak в Am проходит через точку C. Таким образом, d(Ai, Aj) + d(Ak, Am) = d(Ai, Ak) + d(Aj, Am) – 2, что противоречит максимальности суммы расстояний в выбранных парах.
