Сведение к более общему случаю: вершинное покрытие к покрытию множества

Задача о независимом множестве и задача о вершинном покрытии представляют собой две разные категории задач. Задача о независимом множестве может рас- сматриваться как «задача упаковки»: требуется «упаковать» как можно больше вершин с учетом конфликтов (ребер), препятствующих нам в этом.
С другой сторо- ны, задача о вершинном покрытии может рассматриваться как «задача покрытия»: требуется экономно «накрыть» все ребра в графе с использованием минимального количества вершин.

Задача о вершинном покрытии представляет собой задачу покрытия, сформу- лированную «на языке» графов; существует более общая задача покрытия — задача покрытия множества, в которой требуется покрыть произвольное множество объ- ектов с использованием нескольких меньших множеств. Мы можем сформулиро- вать задачу покрытия множества следующим образом:

Задано множеств U из n элементов, набор Sv ..., Sm подмножеств U и число к.

Существует ли набор из не более чем к таких множеств, объединение которых

равно всему множеству U?

Представьте, например, что имеются m программных компонентов и множе- ство U из n функций, которыми должна обладать система. /-й компонент реализует множество S. !Ξ U функций. В задаче покрытия множества требуется включить небольшое количество компонентов, чтобы система поддерживала все n функций.

На рис. 8.2 изображен пример задачи покрытия множества: десять кругов представляют элементы основного множества U, а семь овалов и многоугольни- ков — множества Sp S2, ..., S7. В этом экземпляре задачи присутствует совокупность множеств, объединение которых равно U: например, можно выбрать высокий овал слева с двумя многоугольниками.


На интуитивном уровне понятно, что задача вершинного покрытия является особым случаем задачи покрытия множества: в последнем случае мы пытаемся по- крыть произвольное множество произвольными подмножествами, тогда как в пер- вом ставится частная задача покрытия ребер графа с использованием множеств ребер, инцидентных вершинам. Более того, можно доказать следующее сведение.

(8.6) Вершинное покрытие

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Сведение к более общему случаю: вершинное покрытие к покрытию множества:

  1. Йога на вершине холма
  2. Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
  3. 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
  4. ОТ ЧАСТНОГО К ОБЩЕМУ, НО НЕ НАОБОРОТ
  5. § 28 Утверждается ли давностью такое право, коего приобретение по общему закону воспрещено лицу владеющему?
  6. II. 1. 1. Множества.
  7. II. 2. 2. От единого к множеству.
  8. Вариантов множество.
  9. II. 2. 7. Тетрады и дальнейшее разбиение множеств.
  10. Великое множество «я»
  11. Обида порождает множество болезней
  12. Если вы заблокированы” вас расстраивает сразу множество вещей.
  13. Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
  14. 16.6. Рассекречивание сведений и их носителей
  15. 16.7. Распоряжение сведениями, составляющими государственную тайну
  16. Статья 895. Конфиденциальность сведений о договоре