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

Ссылки сюда (8) →

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

• найти в графе дерево (методом поиска в ширину),
• выкинуть из него листья,
• а оставшееся объявить вершинным покрытием.

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

Стенин Сергей группа 974

То, что предлагает студент, вообще может не дать вершинного покрытия. Покажем это на примере. Рассмотрим полный граф на 4 вершинах. Запустим обход в ширину на любой вершине. Она поместится в очередь. Потом извлекаем из очереди эту вершину и помещаем три остальных в эту очередь. При извлечении этих вершин из очереди ничего не происходит. Получается дерево с корнем на первом уровне и тремя потомками на втором уровне. Если выкинуть из него листья, то останется только одна вершина, которая, очевидно, вершинным покрытием не является вовсе. Так что студент не прав, ибо предложил некорректный алгоритм.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.