Вершинное покрытие

	Определения

Вершинным покрытием S графа G=(V,E) является подмножеством вершин V, которое инцидентно ко всем ребрам негорафа, т.е. для каждого ребра {u,v}ÎE для uÎS или vÎS.

Минимальным вершинным покрытием графа G=(V,E) называется вершинное покрытие минимальной мощности S`.

			Вершинное покрытие и минимальное вершинное покрытие S`={v1, v4}
		Рис.2.9.4. Вершинное покрытие
	Меры

· t(G) – число вершинного покрытия графа. Является числом вершин минимального вершинного покрытия этого графа.

	Класс сложности

Нахождение вершинного покрытия относится к NP-полному классу, а проблема определения минимального вершинного покрытия – NP-полная.

Известны точные решения проблемы минимального вершинного покрытия методом целочисленного программирования или методом ветвей и границ, при этом время расчета растет экспоненциально с увеличением размера графа.

	Жадный алгоритм

Алгоритм G1

Имеется большое число жадных алгоритмов для вычисления «приблизительно» минимального вершинного покрытия. Среди них есть два алгоритма, дающих наилучшее приближение к оптимуму.

1. Начальное значение множества вершинного покрытия S:=0;

2. Выбрать любое ребро {u,v};

3. S:=S È {u,v};

4. Удалить вершины u и v, а также все инцидентные к ним ребра и все изолированные вершины.

5. Повторить 2 до тех пор, пока в графе есть ребра.

Пример

Сложность этого алгоритма – O(n+m), где n –число вершин и m – число ребер графа.

Шаг 1. Выбираем ребро {e,d};

S:={e,d};

b ·

c ·

Удаляем вершины e и d и все инцидентные к ним ребра и изолированные вершины. Получаем подграф

Шаг 2. Выбираем ребро {b,c};

S:={b,c,d,e};

Удаляем все инцидентные ребра и изолированные вершины. Подграф пуст – алгоритм стоп.

Полученное вершинное покрытие неминимально. Минимальным покрытием будет S`={b,d,e}.

	Алгоритм G1

1. Вычислить максимальное или даже наибольшее паросочетание М графа G.

2. Взять вершины максимального или наибольшего паросочетания в качестве вершинного покрытия графа G.

Аппроксимационное отношение алгоритмов G₁и G₂ равно 2.