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