Как можно найти вершинное покрытие графа за линейное время, если граф является деревом?

Question

[Paul]

Здравствуйте. Подскажите, кто в курсе, как решается обозначенная в заголовке задачка или по крайней мере с помощью каких стандартных методов можно её решить. Спасибо.

Answer 1

[Mrrl]

Рекурсия.
Для каждого поддерева ищем два покрытия: P - минимальное покрытие вообще, и Q - минимальное покрытие, содержащее корень. Пусть T - наше дерево, X - его поддеревья, растущие из детей корня. Тогда
Q(T)=1+sum(P(X))
(корень включён, все рёбра, идущие к нему, учтены, в поддеревьях можно выбирать любые покрытия)
P(T)=min(Q(T),sum(Q(X)))
(либо корень не включён - и надо брать покрытия поддеревьев, содержащие корни, либо взять уже построенное покрытие Q).
Для листьев P=0, Q=1.