Реберне покриття

Ребе́рне покриття́ графа — це множина ребер C, така, що кожна вершина графа інцидентна принаймні одному ребру з C.

На малюнку показано реберне покриття двох графів.

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

Зауважимо, що покриття правого графа є не тільки реберним покриттям, але й паруванням. Більш того, це парування є досконалим паруванням — у ньому кожна вершина відповідає рівно одному ребру парування. Досконале парування (якщо існує) завжди є найменшим реберним покриттям.

Задача пошуку найменшого реберного покриття є задачею оптимізації, яка належить до класу задач покриття^[en] і може бути розв'язана за поліноміальний час.

Приклад

Якщо в графі немає ізольованих вершин (тобто вершин степеня 0), то множина всіх ребер є реберним покриттям (але не обов'язково найменшим!). Якщо ізольовані вершини є, реберного покриття в цьому графі не існує.
Повний двочастковий граф K_m,n має число реберного покриття max(m, n).

Властивості

Згідно з другою тотожністю Галлаї, в графі без ізольованих вершин загальне число ребер у найменшому реберному покритті і найбільшому паруванні дорівнює числу вершин графа.

Алгоритм

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

Див. також

Задача про вершинне покриття
Задача про покриття множини — задача про реберне покриття є окремим випадком задачі про покриття множини е лементами генеральної сукупності є вершини, а кожна підмножина покриває рівно два елементи.

Примітки

↑ Гарей і Джонсон (Garey, Johnson, 1979), стор. 79, використовують реберне покриття і вершинне покриття як приклад пари подібних задач, одну з яких можна розв'язати за поліноміальний час, а інша — NP-складна. Див. також стор. 190.
↑ Lawler, 2001, с. 222–223.

Література

Weisstein, Eric W. 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. [1] — Dover Publications, 2001. — ISBN 978-0-486-41453-9. Архівовано з джерела 28 червня 2014
М. Свами, К. Тхуласираман. 9.2 Рёберные покрытия // Графы, сети и алгоритмы. — М. : Мир, 1984. — С. 179—180.

[gt79-1] Гарей і Джонсон (Garey, Johnson, 1979), стор. 79, використовують реберне покриття і вершинне покриття як приклад пари подібних задач, одну з яких можна розв'язати за поліноміальний час, а інша — NP-складна. Див. також стор. 190.

[FOOTNOTELawler2001222–223-2] Lawler, 2001, с. 222–223.

[1]

[2]