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

Чтобы решить задачу, свяжем понятия графов и деревьев. В математике граф состоит из вершин (в нашем случае перекрёстков) и рёбер (ходов между перекрёстками). Нам нужно привести граф к состоянию, в котором он будет представлять собой дерево. ### Шаг 1: Определение свойств дерева Дерево — это связный ациклический граф, который имеет определённые свойства: 1. В дереве с \( n \) вершинами всегда \( n - 1 \) рёбер. 2. Оно не содержит циклов. ### Шаг 2: Применение свойств к задаче В нашей задаче дано: - Количество перекрёстков (вершин) \( n = 11 \) - Количество ходов (рёбер) \( m = 30 \) По свойству дерева, для 11 вершин мы должны иметь \( n - 1 = 11 - 1 = 10 \) рёбер. ### Шаг 3: Вычисление количества рёбер, которые нужно удалить Текущее количество рёбер в графе равно 30. Чтобы добиться того, чтобы граф стал деревом, нам нужно, чтобы осталось 10 рёбер. Следовательно, количество рёбер, которые нужно удалить, можно найти по формуле: \[ \text{Количество рёбер для удаления} = m - (n - 1) = 30 - 10 = 20 \] ### Ответ Таким образом, необходимо перекрыть **20 ходов**, чтобы схема движения представляла собой дерево, не имеющее циклов.