Задача о вершинном покрытии | это... Что такое Задача о вершинном покрытии? (original) (raw)
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Определение
Вершинное покрытие для неориентированного графа это множество его вершин , такое что, у каждого ребра графа хотя бы один из концов входит в S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Пример: Граф, изображённый справа имеет вершинное покрытие размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как и .
Задача о вершинном покрытии требует указать минимально возможный размер вершинного покрытия для заданного графа.
На входе: Граф .
Результат: - размер наименьшего вершинного покрытия графа .
Также вопрос можно ставить, как эквивалентную задачу о разрешении:
На входе: Граф и положительное целое число .
Вопрос: Существует ли вершинное покрытие для размера ?
Задача о вершинном покрытии сходна с задачей о независимом наборе. Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является независимым набором.
Это следует из того, что граф с вершинами имеет вершинное покрытие размера тогда и только тогда, когда данный граф имеет незавимимый набор размера . В этом смысле обе проблемы равнозначны.
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.
NP-полные задачи | |
---|---|
Математика | |
Исследование операций:Оптимизация:Комбинаторная оптимизация | |
Максимизационная задача укладки (упаковки) | Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) |
Теория графов теория множеств | Задача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра |
Алгоритмические задачи | Задача выполнимости булевых формул (в конъюнктивной нормальной форме) |
Логические игры и головоломки | Обобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро |
См. также | Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа |
Классы сложности |