Дано: Связный граф с q ребрами и p вершинами.
Найти: Количество ребер, которые нужно удалить, чтобы получить дерево, содержащее все вершины графа.
Решение:
Число ребер в дереве с p вершинами равно p-1. Таким образом, чтобы из связного графа с p вершинами получить дерево, содержащее все вершины, необходимо удалить q - (p-1) ребер, то есть q - p + 1 ребро.
Ответ:
Для получения дерева, содержащего все вершины связного графа, необходимо удалить q - p + 1 ребро.