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