Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена Category:Решенные задачи на Category:Нерешенные задачи) |
||
Строка 6: | Строка 6: | ||
Прав ли он? Докажите или опровергните. | Прав ли он? Докажите или опровергните. | ||
− | [[Category: | + | [[Category:Нерешенные задачи]] |
Версия 09:53, 26 февраля 2015
Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в глубину),
- выкинуть из него листья (кроме корневого узла).
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.