Олимпиадная задача по графам: отличие маршрутов между городами не больше 1.5 раза
В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.
Разобрать решение
Рассмотрим самый короткий маршрут l, проходящий по всем городам. Пусть он начинается в городе A, заканчивается в городе B, а его длина равна N. Тогда числа на табличках в городах A и B равны N, а все остальные не меньше N. Пусть C – один из оставшихся городов. Он лежит на данном маршруте, поэтому длина пути от C до одного из городов A или B не больше N/2 (без ограничения общности – до A). Рассмотрим маршрут, который выходит из C, доходит кратчайшим образом до A, а затем повторяет маршрут l. Он проходит через все города, и его длина не превосходит
N/2 + N = 3N/2. Следовательно, число на табличке в городе C не больше 3N/2.
Таким образом, все числа на табличках принадлежат отрезку [N, 3N/2], откуда и следует требуемое.
Обсуждение
0Комментариев пока нет.