Interested Article - Рёберное покрытие

Рёберное покрытие графа — это множество рёбер C , такое, что каждая вершина графа инцидентна по меньшей мере одному ребру из C .

Следующий рисунок показывает рёберное покрытие двух графов.

Наименьшее рёберное покрытие — это рёберное покрытие наименьшего размера. Число рёбер в наименьшем рёберном покрытии графа называется числом рёберного покрытия и обозначается через $\rho (G)$ (в книге Свами, Тхулалирамана — $\beta _{1}(G)$ ). Следующий рисунок показывает примеры наименьших рёберных покрытий.

Заметим, что покрытие правого графа является не только рёберным покрытием, но и паросочетанием . Более того, это паросочетание является совершенным паросочетанием — в нём каждая вершина инцидентна в точности одному ребру паросочетания. Совершенное паросочетание (если существует) всегда является наименьшим рёберным покрытием.

Задача поиска наименьшего рёберного покрытия является задачей оптимизации , принадлежит классу и может быть решена за полиномиальное время .

Примеры

Если в графе нет изолированных вершин (т.е. вершин со степенью 0), то множество всех рёбер является рёберным покрытием (но не обязательно наименьшим!). Если изолированные вершины есть, рёберного покрытия в этом графе не существует.
Полный двудольный граф K _m

,

n имеет число рёберного покрытия max( m , n ).

Свойства

Согласно второму тождеству Галлаи , в графе без изолированных вершин общее число рёбер в наименьшем рёберном покрытии и наибольшем паросочетании равно числу вершин графа.

Алгоритмы

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

См. также

Задача о вершинном покрытии
Задача о покрытии множества — задача о рёберном покрытии является частным случаем задачи о покрытии множества – элементами генеральной совокупности являются вершины, а каждое подмножество покрывает ровно два элемента.

Примечания

Гарей и Джонсон ( ), стр. 79, используют рёберное покрытие и вершинное покрытие в качестве примера пары сходных задач, одна из которых может быть решена за полиномиальное время, а другая – NP-трудна. См. также стр. 190.
, с. 222–223.

Литература

Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
Michael R. Garey, David S. Johnson. . — W.H. Freeman, 1979. — ISBN 0-7167-1045-5 .
Eugene L. Lawler. Combinatorial optimization: networks and matroids. — Dover Publications, 2001. — ISBN 978-0-486-41453-9 .
М. Свами, К. Тхуласираман. 9.2 Рёберные покрытия // Графы, сети и алгоритмы. — М. : «Мир», 1984. — С. 179-180.