Задача о вершинном покрытии

Напомним, что вершинным покрытием неориентированного графа

G = (V, E) называется множество C Í V, что для каждого ребра (u, v) графа G по крайней мере один из концов u, v принадлежит C. Размером вершинного покрытия считается количество входящих в него вершин. Задача о вершинном покрытии состоит в нахождении оптимального вершинного покрытия, т.е. вершинного покрытия минимального размера. С алгоритмом AVC (рис. 37.1) можно найти вершинное покрытие, которое хуже оптимального не более чем в 2 раза.

Рис. 37.1

AVG (G)

1. C Æ

2. E^’ Æ

3. while E^’ ¹ Æ

4. do возьмем произвольное ребро {u, v} из E^’

5. C C È {u, v}

6. удалим из E^’ все ребра, инцидентные u или v

7. return C

Работа алгоритма AVC: Из множества E^’,которое сначала совпадает с E, выбирается ребро (u, v) и его концы добавляем в множество C, которое сначала пусто. После чего из E^’ удаляются все ребра, инцидентные u или v. Цикл продолжается, пока E^’ ¹Æ. Время работы алгоритма O(E).

Теорема.Алгоритм AVG работает с ошибкой не более чем в 2 раза.

Доказательство. Покажем, что построенное множество Cобразует вершинное покрытие. Действительно, цикл в строках 3-6 продолжается до тех пор, пока E^’не станет пустым.

Убедимся, что число вершин в C не более чем вдвое хуже оптимального, рассмотрим множество A выбираемых в ходе работы алгоритма ребер. Никакие два ребра не имеют общей вершины (после того, как ребро выбрано в строке 4, все имеющие с ним общую вершину удаляются в строке 6). Поэтому общее число вершин вдвое больше числа ребер в A. Любое вершинное покрытие содержит хотя бы одну вершину каждого выбранного ребра, и для разных ребер эти вершины разные. Таким образом, çA÷ £ êC^*ô, и, следовательно, êC÷ = 2 êAú £ 2 êC*÷.