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