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

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

Определение

Формально, рёберное покрытие графа G — это множество рёбер C, такое, что каждая вершина графа G инцидентна по меньшей мере одному ребру из C. Множество C называется покрытием вершин графа G. Следующий рисунок показывает рёберное покрытие двух графов.

Минимальное рёберное покрытие — это рёберное покрытие наименьшего размера. Число рёбер в минимальном рёберном покрытии графа называется числом рёберного покрытия и обозначается через <math>\rho(G)</math> (в книге Свами, Тхулалирамана — <math>\beta_1(G)</math>). Следующий рисунок показывает примеры минимальных рёберных покрытий.

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

Примеры

• Множество всех рёбер является рёберным покрытием, в предположении, что нет вершин степени 0.
• Полный двудольный граф K_m,n имеет число рёберного покрытия max(m, n).

Алгоритмы

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

С другой стороны, близкая задача нахождения минимального вершинного покрытия является NP-трудной задачей

См. также

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

Литература

• Weisstein, Eric W. [mathworld.wolfram.com/EdgeCover.html Edge Cover] (англ.) на сайте Wolfram MathWorld.
• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — 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.

Отрывок, характеризующий Рёберное покрытие

В ту же ночь, откланявшись военному министру, Болконский ехал в армию, сам не зная, где он найдет ее, и опасаясь по дороге к Кремсу быть перехваченным французами.
В Брюнне всё придворное население укладывалось, и уже отправлялись тяжести в Ольмюц. Около Эцельсдорфа князь Андрей выехал на дорогу, по которой с величайшею поспешностью и в величайшем беспорядке двигалась русская армия. Дорога была так запружена повозками, что невозможно было ехать в экипаже. Взяв у казачьего начальника лошадь и казака, князь Андрей, голодный и усталый, обгоняя обозы, ехал отыскивать главнокомандующего и свою повозку. Самые зловещие слухи о положении армии доходили до него дорогой, и вид беспорядочно бегущей армии подтверждал эти слухи.
«Cette armee russe que l'or de l'Angleterre a transportee, des extremites de l'univers, nous allons lui faire eprouver le meme sort (le sort de l'armee d'Ulm)», [«Эта русская армия, которую английское золото перенесло сюда с конца света, испытает ту же участь (участь ульмской армии)».] вспоминал он слова приказа Бонапарта своей армии перед началом кампании, и слова эти одинаково возбуждали в нем удивление к гениальному герою, чувство оскорбленной гордости и надежду славы. «А ежели ничего не остается, кроме как умереть? думал он. Что же, коли нужно! Я сделаю это не хуже других».
Князь Андрей с презрением смотрел на эти бесконечные, мешавшиеся команды, повозки, парки, артиллерию и опять повозки, повозки и повозки всех возможных видов, обгонявшие одна другую и в три, в четыре ряда запружавшие грязную дорогу. Со всех сторон, назади и впереди, покуда хватал слух, слышались звуки колес, громыхание кузовов, телег и лафетов, лошадиный топот, удары кнутом, крики понуканий, ругательства солдат, денщиков и офицеров. По краям дороги видны были беспрестанно то павшие ободранные и неободранные лошади, то сломанные повозки, у которых, дожидаясь чего то, сидели одинокие солдаты, то отделившиеся от команд солдаты, которые толпами направлялись в соседние деревни или тащили из деревень кур, баранов, сено или мешки, чем то наполненные.
На спусках и подъемах толпы делались гуще, и стоял непрерывный стон криков. Солдаты, утопая по колена в грязи, на руках подхватывали орудия и фуры; бились кнуты, скользили копыта, лопались постромки и надрывались криками груди. Офицеры, заведывавшие движением, то вперед, то назад проезжали между обозами. Голоса их были слабо слышны посреди общего гула, и по лицам их видно было, что они отчаивались в возможности остановить этот беспорядок. «Voila le cher [„Вот дорогое] православное воинство“, подумал Болконский, вспоминая слова Билибина.
Желая спросить у кого нибудь из этих людей, где главнокомандующий, он подъехал к обозу. Прямо против него ехал странный, в одну лошадь, экипаж, видимо, устроенный домашними солдатскими средствами, представлявший середину между телегой, кабриолетом и коляской. В экипаже правил солдат и сидела под кожаным верхом за фартуком женщина, вся обвязанная платками. Князь Андрей подъехал и уже обратился с вопросом к солдату, когда его внимание обратили отчаянные крики женщины, сидевшей в кибиточке. Офицер, заведывавший обозом, бил солдата, сидевшего кучером в этой колясочке, за то, что он хотел объехать других, и плеть попадала по фартуку экипажа. Женщина пронзительно кричала. Увидав князя Андрея, она высунулась из под фартука и, махая худыми руками, выскочившими из под коврового платка, кричала:
– Адъютант! Господин адъютант!… Ради Бога… защитите… Что ж это будет?… Я лекарская жена 7 го егерского… не пускают; мы отстали, своих потеряли…