Русская Википедия:Рёберное покрытие
Рёберное покрытие графа — это множество рёбер C, такое, что каждая вершина графа инцидентна по меньшей мере одному ребру из C.
Шаблон:Пары задач покрытия/упаковкиСледующий рисунок показывает рёберное покрытие двух графов.
Наименьшее рёберное покрытие — это рёберное покрытие наименьшего размера. Число рёбер в наименьшем рёберном покрытии графа называется числом рёберного покрытия и обозначается через <math>\rho(G)</math> (в книге Свами, Тхулалирамана — <math>\beta_1(G)</math>). Следующий рисунок показывает примеры наименьших рёберных покрытий.
Заметим, что покрытие правого графа является не только рёберным покрытием, но и паросочетанием. Более того, это паросочетание является совершенным паросочетанием — в нём каждая вершина инцидентна в точности одному ребру паросочетания. Совершенное паросочетание (если существует) всегда является наименьшим рёберным покрытием.
Задача поиска наименьшего рёберного покрытия является задачей оптимизации, принадлежит классу Шаблон:Не переведено 5 и может быть решена за полиномиальное время.
Примеры
- Если в графе нет изолированных вершин (т.е. вершин со степенью 0), то множество всех рёбер является рёберным покрытием (но не обязательно наименьшим!). Если изолированные вершины есть, рёберного покрытия в этом графе не существует.
- Полный двудольный граф Km,n имеет число рёберного покрытия max(m, n).
Свойства
- Согласно второму тождеству Галлаи, в графе без изолированных вершин общее число рёбер в наименьшем рёберном покрытии и наибольшем паросочетании равно числу вершин графа.
Алгоритмы
Наименьшее рёберное покрытие можно найти за полиномиальное время путём нахождения наибольшего паросочетания с последующим добавлением рёбер с помощью жадного алгоритма для покрытия оставшихся вершин [1]Шаблон:Sfn. На следующем рисунке наибольшее паросочетание показано красным цветом. Дополнительные рёбра, которые добавлены для покрытия непокрытых вершин, показаны синим цветом (в графе справа наибольшее паросочетание является совершенным паросочетанием, в котором все вершины уже покрыты, так что нет необходимости в дополнительных рёбрах.)
См. также
- Задача о вершинном покрытии
- Задача о покрытии множества — задача о рёберном покрытии является частным случаем задачи о покрытии множества – элементами генеральной совокупности являются вершины, а каждое подмножество покрывает ровно два элемента.
Примечания
Литература
- ↑ Гарей и Джонсон Шаблон:Harv, стр. 79, используют рёберное покрытие и вершинное покрытие в качестве примера пары сходных задач, одна из которых может быть решена за полиномиальное время, а другая – NP-трудна. См. также стр. 190.
