Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2
Материал из DISCOPAL
< Жадный алгоритм в задачах о покрытии | Задачи
Версия от 07:42, 18 апреля 2013; StasFomin (обсуждение | вклад)
Студент предложил для задачи вершинного покрытия приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в ширину),
- выкинуть из него листья,
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
[ Иерархический вид ]Комментарии
Войдите, чтобы комментировать.