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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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