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

Материал из DISCOPAL
Перейти к: навигация, поиск

Цыганова Светлана, 974 гр.

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

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

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

Решение

Во-первых, докажем, что полученное таким образом множество вершин будет вершинным покрытием (не всегда минимальным, правда). Если это не так, то получалось бы, что алгоритм поиска в глубину давал бы цикл, что невозможно.

Теперь покажем, что соблюдается заданная точность. Для этого рассмотрим полученное студентом дерево. Очевидно, что для каждого ребра в этом дереве хотя бы одна вершина должна лежать в минимальном вершинном покрытии. Тогда число вершин в найденном дереве отличается не больше, чем в 2 раза от числа вершин минимального вершинного покрытия, следовательно, соблюдена заданная точность.

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

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

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