Question

Дан полный двудольный граф, у которого в первом множестве 10 вершин, а во втором 12 вершин. Сколько рёбер нужно удалить из этого графа, чтобы получить остовное дерево?

Answer 1

Дано: полный двудольный граф K(10, 12), где n1 = 10, n2 = 12.

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

Решение:  
1. Полный двудольный граф K(n1, n2) содержит n1 * n2 рёбер. В данном случае количество рёбер:  
   R = n1 * n2 = 10 * 12 = 120.

2. Остовное дерево на 22 вершинах (10 + 12) содержит V - 1 рёбер, где V - общее количество вершин. Таким образом:  
   T = 22 - 1 = 21.

3. Чтобы получить остовное дерево, нужно удалить:  
   U = R - T = 120 - 21 = 99.

Ответ: нужно удалить 99 рёбер.