WikiSort.ru - Не сортированное

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

Определение

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

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

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

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

На входе: Граф ${\displaystyle G}$ .

Результат: ${\displaystyle k}$  — размер наименьшего вершинного покрытия ${\displaystyle S}$ графа ${\displaystyle G}$ .

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

На входе: Граф ${\displaystyle G}$ и положительное целое число ${\displaystyle k}$ .

Вопрос: Существует ли вершинное покрытие ${\displaystyle S}$ для ${\displaystyle G}$ размера ${\displaystyle k}$ ?

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

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

NP-полнота

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

См. также

• Теорема Кёнига утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.

Ссылки

• A compendium of NP optimization problems
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring

Литература

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