• 50 БАЛЛОВ!
    В государстве 10 городов, некоторые пары которых соединены
    беспосадочными авиалиниями так, что из любого города можно долететь
    до любого другого (возможно, с пересадками). Расстоянием между
    городами А и Б назовем минимальное количество перелётов, за которое
    можно долететь из А в Б. Министерство транспорта открыло новую
    авиалинию между двумя городами, расстояние между которыми до этого
    было наибольшим. Может ли после этого расстояние между некоторыми
    двумя городами оказаться большим 5?

Ответы 1

  • Нет, не может. Если все города соединены между собой их можно выстроить цепочкой (или будет несколько более коротких цепей). После этого мы соединяем два конца этой цепи. Это два самых удаленных города - один в начале цепи, другой в конце.) Теперь по цепи можно двигаться в по кольцу в прямом и обратном направлении. Тогда если в прямом направлении будет больше 5 городов, то в обратном направлении будет меньше пяти городов. Если цепей две или более, то замыкается самая длинная цепь, а короткая цепь будет из пяти или менее пяти городов (т.к. всего городов 10.)
    • Автор:

      honorio
    • 5 лет назад
    • 0
  • Добавить свой ответ

Войти через Google

или

Забыли пароль?

У меня нет аккаунта, я хочу Зарегистрироваться

How much to ban the user?
1 hour 1 day 100 years