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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача о вершинном покрытииNP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.

Определение[править | править вики-текст]

6n-graf.svg

Вершинное покрытие для неориентированного графа G = (V, E) это множество его вершин S, такое что, у каждого ребра графа хотя бы один из концов входит в S.


Размером (size) вершинного покрытия называется число входящих в него вершин.

Пример: Граф, изображённый справа, имеет вершинное покрытие \{1,3,5,6\} размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как \{2,4,5\} и \{1,2,4\}.

Задача о вершинном покрытии требует указать минимально возможный размер  k  вершинного покрытия для заданного графа.

На входе: Граф G.
Результат: k - размер наименьшего вершинного покрытия S графа G.

Также вопрос можно ставить, как эквивалентную задачу о разрешении:

На входе: Граф G и положительное целое число k.
Вопрос: Существует ли вершинное покрытие S для G размера k?

Задача о вершинном покрытии сходна с задачей о независимом наборе. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение  \bar S = V \setminus S является независимым набором.

Это следует из того, что граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет незавимимый набор размера n-k. В этом смысле обе проблемы равнозначны.

NP-полнота[править | править вики-текст]

Поскольку задача о вершинном покрытии является NP-полной, то, к сожалению, неизвестны алгоритмы для её решения за полиномиальное время. Однако существуют алгоритмы, дающие «приближённое» решение этой задачи за полиномиальное время — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Томас Х. Кормен и др. Глава 36. NP-полнота // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 866.