Как найти набор отзывов с весом не более k

Question

Набор обратной связи любого неориентированного взвешенного графа представляет собой подмножество ребер, так что после удаления ребер в подмножестве оставшийся граф является ациклическим c.

При условии G = (V, E) , неориентированный и взвешенный график и целое число k, как я могу определить, существует ли набор обратной связи с общим весом не более k?

Спасибо!

Answer 1

Минимальный набор обратной связи никогда не будет содержать ребро, которое разъединяет два компонента графа, поэтому удаление набора обратной связи не изменит подключенные компоненты, но это сделает каждый подключенный компонент acycli c.

Если неориентированный граф подключен и acycli c, то это дерево, поэтому:

Для каждого связанного компонента в графе найдите максимум весовое остовное дерево. Вы можете использовать любой из алгоритмов связующего дерева с минимальным весом, просто отрицая все веса.

Ребра, которых нет ни в одном из связующих деревьев с максимальным весом, являются набором обратной связи с минимальным весом.

Чтобы найти все деревья максимального веса, я рекомендую использовать алгоритм Крускала на всем графе с ребрами, отсортированными по убыванию веса, так как он найдет их все сразу. Затем просто выберите все ребра, которых нет ни в одном дереве.