Краевая крышка

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

Определение

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

Минимальное покрытие кромок — это покрытие кромок наименьшего возможного размера. Число покрытия ребер $ρ (G)$ — это размер минимального покрытия ребер. На следующем рисунке показаны примеры минимальных покрытий ребер (множество $C$ снова отмечено красным).

Обратите внимание, что рисунок справа — это не только краевая крышка, но и соответствующая . В частности, это идеальное паросочетание : паросочетание $M$ в котором каждая вершина инцидентна ровно одному ребру в $M.$ , Совершенное паросочетание (если оно существует) всегда представляет собой минимальное покрытие ребер.

Примеры

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

Алгоритмы

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

С другой стороны, соответствующая задача поиска наименьшего вершинного покрытия является NP-трудной задачей. ^[1]

Глядя на изображение, уже становится очевидно, почему при заданном минимальном покрытии кромки $C$ и максимальное соответствие $M$ , позволяя $c$ и $m$ быть числом ребер в $C$ и $M$ соответственно имеем: ^[3] $|V|=c+m$ . Действительно, $C$ содержит максимальное паросочетание, поэтому ребра $C$ можно разложить между $m$ ребра максимального паросочетания, покрывающие $2m$ вершины и $c-m$ другие ребра, каждое из которых закрывает одну другую вершину. Таким образом, как $C$ охватывает все $|V|$ вершины, у нас есть $|V|=2m+(c-m)$ давая желаемое равенство.

См. также

Крышка вершины
Покрытие множества - проблема покрытия ребер является частным случаем проблемы покрытия множества: элементы вселенной являются вершинами, и каждое подмножество покрывает ровно два элемента.

Примечания

^ Jump up to: ^а ^б Гари и Джонсон (1979) , с. 79 использует покрытие ребер и покрытие вершин как один из примеров пары подобных задач, одна из которых может быть решена за полиномиальное время, а другая является NP-трудной. См. также стр. 190.
^ Лоулер, Юджин Л. (2001), Комбинаторная оптимизация: сети и матроиды , Dover Publications, стр. 222–223, ISBN 978-0-486-41453-9 .
^ «Докажите, что сумма минимального покрытия ребер и максимального соответствия равна количеству вершин» . Математический обмен стеками . Проверено 18 февраля 2024 г.

Ссылки

[gt79-1] Jump up to: ^а ^б Гари и Джонсон (1979) , с. 79 использует покрытие ребер и покрытие вершин как один из примеров пары подобных задач, одна из которых может быть решена за полиномиальное время, а другая является NP-трудной. См. также стр. 190.

[2] Лоулер, Юджин Л. (2001), Комбинаторная оптимизация: сети и матроиды , Dover Publications, стр. 222–223, ISBN 978-0-486-41453-9 .

[3] «Докажите, что сумма минимального покрытия ребер и максимального соответствия равна количеству вершин» . Математический обмен стеками . Проверено 18 февраля 2024 г.

[1]

[2]

[3]