Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2
Цыганова Светлана, 974 гр.
Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в глубину),
- выкинуть из него листья (кроме корневого узла).
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
Решение
Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно.
Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии. Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.