Сколько рёбер нужно удалить, чтобы получить остовное дерево, из графа:
а) куба; б) тетраэдра?
от

1 Ответ

Дано:

а) Граф куба; б) Граф тетраэдра.

Найти:

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

Решение:

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

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

б) Тетраэдр имеет 4 вершины и 6 рёбер.  
Для остовного дерева нужно 4 - 1 = 3 рёбер.  
Количество рёбер, которые нужно удалить: 6 - 3 = 3.

Ответ: а) 5 рёбер; б) 3 ребра.
от