Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 6: | Строка 6: | ||
Прав ли он? Докажите или опровергните. | Прав ли он? Докажите или опровергните. | ||
| − | [[Category: | + | [[Category:Проблемные задачи]] |
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
Текущая версия на 17:13, 19 мая 2015
Студент предложил для задачи вершинного покрытия приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в ширину),
- выкинуть из него листья,
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.