Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2

Ссылки сюда (6) →

Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:

• найти в графе дерево (методом поиска в глубину),
• выкинуть из него листья (кроме корневого узла).
• а оставшееся объявить вершинным покрытием.

Прав ли он? Докажите или опровергните.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.