В некоторой стране 25 городов, причём каждый соединён с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в любой другой?
More Questions From This User See All
Copyright © 2024 SCHOLAR.TIPS - All rights reserved.
Answers & Comments
Verified answer
В стране 25 * 24 / 2 = 300 дорог.
Если оставить 23 или меньше дорог, как минимум один город будет не связан с другими (выбираем произвольный город и начинаем открывать дороги, каждое открытие добавляет к списку городов, в которые можно добраться, не более чем 1 новый город), а 24 дороги оставить можно: например, выбрать один город и связать его с остальными.
Закрыть можно не более 300 - 24 = 276 дорог.