В теории графов , край крышки из графика представляет собой набор ребер таким образом, что каждая вершина графа падает , по меньшей мере , одного края набора. В информатике , то минимальная задача край крышки является проблемой нахождения краев крышки минимального размера. Это задача оптимизации, которая относится к классу покрывающих задач и может быть решена за полиномиальное время .
Определение
Формально ребро крышки графа G представляет собой множество ребер C таким образом, что каждая вершина G падает с , по меньшей мере , одного края в C . Множество C называется покрыть вершины G . На следующем рисунке показаны примеры покрытий ребер в двух графах.
Минимальная кромка покрытие ребро покрытия минимально возможного размера. Номер покрытия кромки это размер минимального краевого покрытия. На следующем рисунке показаны примеры минимального покрытия кромок.
Обратите внимание, что рисунок справа - это не только крайняя крышка, но и совпадение . В частности, это идеальное соответствие : комбинационные М , в котором каждая вершина падает ровно с одним ребром в M . Идеальное совпадение (если оно существует) - это всегда минимальное краевое покрытие.
Примеры
- Множество всех ребер является краевым покрытием, если предположить, что нет вершин нулевой степени.
- Полный двудольный граф К м , п имеет края покрытия число макс ( м , п ).
Алгоритмы
Наименьшее краевое покрытие можно найти за полиномиальное время , найдя максимальное совпадение и жадно расширив его так, чтобы были покрыты все вершины. [1] [2] На следующем рисунке максимальное соответствие отмечено красным; дополнительные ребра, которые были добавлены для покрытия несовпадающих узлов, отмечены синим цветом. (На рисунке справа показан граф, в котором максимальное совпадение является идеальным совпадением ; следовательно, он уже охватывает все вершины, и никаких дополнительных ребер не требовалось.)
С другой стороны, связанная с этим проблема поиска наименьшего вершинного покрытия является NP-трудной задачей. [1]
Смотрите также
- Крышка Vertex
- Установить покрытие - проблема краевого покрытия является частным случаем задачи множества покрытий: элементы вселенной являются вершинами, и каждое подмножество покрывает ровно два элемента.
Заметки
- ^ a b Garey & Johnson (1979) , стр. 79, использует краевое покрытие и вершинное покрытие как один из примеров пары похожих задач, одна из которых может быть решена за полиномиальное время, а другая является NP-трудной. См. Также стр. 190.
- ^ Лоулер, Юджин Л. (2001), Комбинаторная оптимизация: сети и матроиды , Dover Publications, стр. 222–223, ISBN 978-0-486-41453-9.
Рекомендации
- Вайсштейн, Эрик В. "Edge Cover" . MathWorld .
- Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5.