В теории графов , край крышки из графика представляет собой набор ребер таким образом, что каждая вершина графа падает , по меньшей мере , одного края набора. В информатике , то минимальная задача край крышки является проблемой нахождения краев крышки минимального размера. Это задача оптимизации, которая относится к классу покрывающих задач и может быть решена за полиномиальное время .
Определение [ править ]
Формально ребро крышки графа 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.
