Дано:
а) Граф куба; б) Граф тетраэдра.
Найти:
Количество рёбер, которые нужно удалить, чтобы получить остовное дерево.
Решение:
Для получения остовного дерева из графа с n вершинами нужно, чтобы количество рёбер было n - 1.
а) Куб имеет 8 вершин и 12 рёбер.
Для остовного дерева нужно 8 - 1 = 7 рёбер.
Количество рёбер, которые нужно удалить: 12 - 7 = 5.
б) Тетраэдр имеет 4 вершины и 6 рёбер.
Для остовного дерева нужно 4 - 1 = 3 рёбер.
Количество рёбер, которые нужно удалить: 6 - 3 = 3.
Ответ: а) 5 рёбер; б) 3 ребра.