Внекоторой стране 25 городов, причём каждый соединён с каждым дорогой. какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в любой другой?

197

369

Посмотреть ответы 2

Ответы на вопрос:

egorfadeev02

Математика

4,7(94 оценок)

в стране 25 * 24 / 2 = 300 дорог.

если оставить 23 или меньше дорог, как минимум один город будет не связан с другими (выбираем произвольный город и начинаем открывать дороги, каждое открытие добавляет к списку городов, в которые можно добраться, не более чем 1 новый город), а 24 дороги оставить можно: например, выбрать один город и связать его с остальными.

закрыть можно не более 300 - 24 = 276 дорог.