Question

Сколько рёбер нужно удалить из связного графа, чтобы получить остовное дерево, если в данном графе:
а)  8 вершин и 14 рёбер; б) 13 вершин и 18 рёбер?

Answer 1

Дано:

а) 8 вершин и 14 рёбер;  
б) 13 вершин и 18 рёбер.

Найти:

Количество рёбер, которые нужно удалить, чтобы получить остовное дерево.

Решение:

Для получения остовного дерева из графа с n вершинами нужно, чтобы количество рёбер было n - 1.

а) Для 8 вершин нужно 8 - 1 = 7 рёбер.  
Количество рёбер, которые нужно удалить: 14 - 7 = 7.

б) Для 13 вершин нужно 13 - 1 = 12 рёбер.  
Количество рёбер, которые нужно удалить: 18 - 12 = 6.

Ответ: а) 7 рёбер; б) 6 рёбер.