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