Лекция: Вершинное покрытие

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

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

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

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

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

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

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

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

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

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

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

S:={e,d};

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

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

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

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

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

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

Аппроксимационное отношение алгоритмов G1и G2 равно 2.