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

Чтобы сохранить возможность добраться из любого города в любой другой, необходимо оставить как минимум одно соединение (авиалинию) между каждой парой городов. В этом случае можно рассматривать связь между городами как граф, где города – это вершины, а авиалинии – ребра.

Для обеспечения связности графа с \( n \) вершинами (в нашем случае \( n = 30 \)) минимально необходимое количество рёбер (авиалиний), чтобы граф оставался связным, составляет \( n - 1 \).

Таким образом, в нашем случае необходимо оставить как минимум \( 30 - 1 = 29 \) авиалиний.

Каждая пара городов соединена прямыми авиалиниями, и общее количество авиалиний при полной связности (полном графе) составляет \( \frac{n(n-1)}{2} \). Для 30 городов это:

\[ \frac{30 \times 29}{2} = 435 \]

Теперь, чтобы найти наибольшее количество авиалиний, которое можно закрыть, вычтем необходимое количество рёбер (29) из общего количества.

\[ 435 - 29 = 406 \]

Следовательно, наибольшее количество авиалиний, которое можно закрыть, составляет 406.