Попробуйте ГДЗ по фото

Вопрос:

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

Фотография

Ответ ассистента

1. Сначала найдём общее количество дорог в стране. Каждая дорога соединяет два города, поэтому сумма всех выходящих дорог будет в два раза больше их реального количества. Сумма выходящих дорог: $20 \cdot 2 + 10 \cdot 4 = 40 + 40 = 80$. Общее количество дорог: $80 : 2 = 40$. 2. Чтобы из любого города можно было добраться в любой другой (граф оставался связным), минимальное количество дорог для $n$ городов должно быть равно $n - 1$. В нашей задаче $n = 30$, значит, минимум нужно оставить: $30 - 1 = 29$ дорог. 3. Найдём количество дорог, которые можно закрыть: $40 - 29 = 11$. **Ответ: 11**

Другие решения

Что ещё искали пользователи