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

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

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

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

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

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

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

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

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

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

• 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.