82. Сколько рёбер нужно удалить из графа, изображённого на рисунке 57, чтобы получилось дерево? Удалите их и перерисуйте полученное дерево в тетрадь.

Для решения этих задач важно понимать определение дерева: дерево — это связный граф без циклов. Если в графе $n$ вершин, то в дереве всегда ровно $n-1$ ребро. ### Задача 82 Чтобы получить дерево из связного графа, нужно оставить такое количество рёбер, чтобы граф остался связным, но циклы исчезли. Количество удаляемых рёбер равно $E - (V - 1)$, где $E$ — текущее число рёбер, $V$ — число вершин. * **Рис. 57, а):** Граф — это шестиугольник (цикл). $V=6, E=6$. Нужно удалить $6 - (6-1) = 1$ ребро. После удаления любого ребра получится путь (линия из 6 вершин). * **Рис. 57, б):** Это полный граф $K_5$. $V=5, E=10$. Нужно удалить $10 - (5-1) = 6$ рёбер. Чтобы получилось дерево, можно оставить, например, только рёбра, образующие путь или «звезду». * **Рис. 57, в):** Граф состоит из двух треугольников, соединенных в одной общей вершине. $V=5$ (центральная + 4 боковых), $E=6$. Нужно удалить $6 - (5-1) = 2$ ребра. Удалив по одному ребру из каждого треугольника, мы «разорвем» циклы и получим дерево. ### Задача 83 На рисунке 58 видны разрозненные компоненты связности. Чтобы превратить несвязный граф в дерево, нужно соединить все компоненты связности. Если у вас $k$ компонент, нужно добавить $k-1$ ребро, чтобы объединить их в одно дерево.