11-10-2023
В Информатике, задача о вершинном покрытии является NP-полной задачей в области теории графов. Также часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Содержание |
Вершинное покрытие для неориентированного графа это множество его вершин , такое что, у каждого ребра графа хотя бы один из концов входит в S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Пример: Граф, изображённый справа имеет вершинное покрытие размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как и .
Задача о вершинном покрытии требует указать минимально возможный размер вершинного покрытия для заданного графа.
Также вопрос можно ставить, как эквивалентную задачу о разрешении:
Задача о вершинном покрытии сходна с задачей о независимом наборе. Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является незавимимым набором.
Это следует из того, что граф с вершинами имеет вершинное покрытие размера тогда и только тогда, когда данный граф имеет незавимимый набор размера . В этом смысле обе проблемы равнозначны.
Поскольку задача о вершинном покрытии является NP-полной, то, к сожалению, неизвестны алгоритмы для её решения за полиномиальное время. Однако, существуют алгоритмы, дающие «приближённое» решение этой задачи за полиномиальное время — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Задача о вершинном покрытии.