Для решения данной задачи нужно использовать понятия теории графов. Мы можем представить города как вершины графа, а подземные ходы между ними — как рёбра этого графа. Поскольку каждый город соединён с каждым другим городом, у нас имеется полный граф на 60 вершинах, также известный как граф ( K_{60} ).
Шаг 1: Определение количества рёбер в полном графе
Общее количество рёбер ( E ) в полном графе с ( n ) вершинами можно рассчитать по формуле:
[
E = \frac{n(n-1)}{2}
]
Подставим ( n = 60 ):
[
E = \frac{60 \times 59}{2} = 1770
]
Таким образом, в нашем графе 1770 рёбер.
Шаг 2: Определение условий задачи
Наша задача состоит в том, чтобы закрыть как можно больше рёбер (подземных ходов) на ремонт, сохранив возможность достичь из любого города (вершины) другого города. Это означает, что граф должен оставаться связным.
Шаг 3: Определение минимального числа рёбер для связности
Для того чтобы граф оставался связным, минимальное количество рёбер должно составлять ( n - 1 ), где ( n ) — количество вершин. В нашем случае:
[
n - 1 = 60 - 1 = 59
]
Это означает, что в любом связном графе из 60 вершин должно быть не менее 59 рёбер.
Шаг 4: Расчёт рёбер, которые можно закрыть
Исходя из того, что в полном графе 1770 рёбер и чтобы сохранить связность нам необходимо 59 рёбер, можно вычислить, сколько рёбер можно закрыть:
[
\text{Количество рёбер, которые можно закрыть} = E - (n - 1) = 1770 - 59 = 1711
]
Итог
Таким образом, максимальное количество подземных ходов, которые можно закрыть на ремонт, так чтобы из любого города можно было проехать в любой другой, составляет 1711.
