Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2
Материал из DISCOPAL
< Жадный алгоритм в задачах о покрытии | Задачи
Версия от 19:48, 8 ноября 2014; SteninSergey (обсуждение | вклад)
Студент предложил для задачи вершинного покрытия приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в ширину),
- выкинуть из него листья,
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
Стенин Сергей группа 974
То, что предлагает студент, вообще может не дать вершинного покрытия. Покажем это на примере. Рассмотрим полный граф на 4 вершинах. Запустим обход в ширину на любой вершине. Она поместится в очередь. Потом извлекаем из очереди эту вершину и помещаем три остальных в эту очередь. При извлечении этих вершин из очереди ничего не происходит. Получается дерево с корнем на первом уровне и тремя потомками на втором уровне. Если выкинуть из него листья, то останется только одна вершина, которая, очевидно, вершинным покрытием не является вовсе. Так что студент не прав, ибо предложил некорректный алгоритм.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.