Разделы 
Дополнительно
Задача по математике - 1955
2019-01-22 
В стране несколько городов, некоторые пары городов соединены дорогами, причем между любыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из любого города попасть в любой другой.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам. В этом графе между любыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (такой граф называется деревом). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (такие вершины называются висячими) - пусть это вершины $A_1,A_2,\cdots, A_{100}$ Для каждой пары висячих вершин $A_i$ и $A_j$ существует единственный путь между ними, назовем количество ребер на этом пути расстоянием между этими вершинами и будем обозначать через $d(A_i, A_j)$. Из конечности числа способов разбить эти 100 вершин на 50 пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми ребрами (остальные ребра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа (т. е., возможность из любой вершины попасть в любую другую).
Предположим противное, пусть при удалении ребра между вершинами $B$ и $C$ граф распался на две части, которые не связаны между собой. Нетрудно заметить, что удаленное ребро было старым, в одной из полученных частей находится вершина $B$, а в другой - вершина $C$. Очевидно, в каждой части должна быть вершина, из которой выходит ровно одно старое ребро, и каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины $A_i$ и $A_j$, а в другой - соединяющее вершины $A_k$ и $A_m$. Однако в этом случае нетрудно проверить, что
$d(A_i , A_j) + d(A_k , A_m) < d(A_i, A_k) + d(A_j , A_m)$,
что противоречит максимальности суммы расстояний в выбранных парах. Следовательно, при удалении ребра $BC$ возможность попасть из любой вершины в любую другую должна сохраниться.
В стране несколько городов, некоторые пары городов соединены дорогами, причем между любыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из любого города попасть в любой другой.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам. В этом графе между любыми двумя вершинами есть единственный путь, следовательно, в нем нет циклов (такой граф называется деревом). По условию, в этом графе есть 100 вершин, из которых выходит ровно одно ребро (такие вершины называются висячими) - пусть это вершины $A_1,A_2,\cdots, A_{100}$ Для каждой пары висячих вершин $A_i$ и $A_j$ существует единственный путь между ними, назовем количество ребер на этом пути расстоянием между этими вершинами и будем обозначать через $d(A_i, A_j)$. Из конечности числа способов разбить эти 100 вершин на 50 пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении 50 новыми ребрами (остальные ребра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа (т. е., возможность из любой вершины попасть в любую другую).
Предположим противное, пусть при удалении ребра между вершинами $B$ и $C$ граф распался на две части, которые не связаны между собой. Нетрудно заметить, что удаленное ребро было старым, в одной из полученных частей находится вершина $B$, а в другой - вершина $C$. Очевидно, в каждой части должна быть вершина, из которой выходит ровно одно старое ребро, и каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины $A_i$ и $A_j$, а в другой - соединяющее вершины $A_k$ и $A_m$. Однако в этом случае нетрудно проверить, что
$d(A_i , A_j) + d(A_k , A_m) < d(A_i, A_k) + d(A_j , A_m)$,
что противоречит максимальности суммы расстояний в выбранных парах. Следовательно, при удалении ребра $BC$ возможность попасть из любой вершины в любую другую должна сохраниться.
