Упр.86 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 86. Все 30 городов некоторого государства соединены прямыми авиалиниями. Правительство решило сократить число авиалиний. Какое наибольшее их количество можно закрыть, чтобы можно было по-прежнему долететь из любого города в любой другой, но, возможно, с пересадками?

Чтобы из любого города можно было добраться в любой другой, сеть авиалиний должна оставаться связной. Минимальное число авиалиний, достаточное для связи 30 городов, равно числу рёбер в дереве:

$$30-1=29$$

Всего при полном соединении всех городов число авиалиний равно числу рёбер полного графа:

$$\frac{30\cdot(30-1)}{2}=435$$

Тогда наибольшее число авиалиний, которые можно закрыть, равно

$$435-29=406$$

Ответ

$$406$$