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

Предыдущий
вопрос Следующий
вопрос

Для того чтобы из каждого города можно было бы попасть в любой другой, нам нужно сохранить связность графа городов. Это означает, что нам нужно закрыть все дороги кроме одной между каждой парой городов.

Итак, количество дорог, которые нужно закрыть на ремонт, равно общему числу дорог минус количество городов.
Общее число дорог = 30C2 = 435 (так как количество способов выбрать 2 города из 30)
Количество городов = 30

Таким образом, количество дорог, которые нужно закрыть на ремонт, равно 435 - 30 = 405.

Итак, нам нужно закрыть 405 дорог для того, чтобы из каждого города можно было бы попасть в любой другой.