Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2 — различия между версиями

Версия 22:18, 24 декабря 2014

Студент предложил для задачи вершинного покрытия приближенный алгоритм с точностью ½:

Прав ли он? Докажите или опровергните.

@@ Строка 6: / Строка 6: @@
 Прав ли он? Докажите или опровергните.
-[[Category:На проверку]]
+[[Category:Решенные задачи]]
-=Стенин Сергей группа 974=
+<!--Вообще-то, решения уже есть-->
-То, что предлагает студент, вообще может не дать вершинного покрытия. Покажем это на примере. Рассмотрим полный граф на 4 вершинах. Запустим обход в ширину на любой вершине. Она поместится в очередь. Потом извлекаем из очереди эту вершину и помещаем три остальных в эту очередь. При извлечении этих вершин из очереди ничего не происходит. Получается дерево с корнем на первом уровне и тремя потомками на втором уровне. Если выкинуть из него листья, то останется только одна вершина, которая, очевидно, вершинным покрытием не является вовсе. Так что студент не прав, ибо предложил некорректный алгоритм.