Число реберного покриття

Число́ ребе́рного покриття́ графа $G$ — розмір найменшого реберного покриття в ньому.

Якщо в графі $G$ є ізольовані вершини (тобто вершини зі степенем 0), то реберного покриття не існує, тому й число реберного покриття не визначене.

У довільному графі без ізольованих вершин число реберного покриття можна знайти за допомогою алгоритму Едмондса для парувань за час $O(|E||V|^{2})$ і подальшого додавання ребер, що покривають не насичені найбільшим паруванням вершини.

У графі $G=(V,E)$ без ізольованих вершин число реберного покриття $\rho (G)$ пов'язане з числом парування $\nu (G)$ другою тотожністю Галлаї: $\nu (G)+\rho (G)=|V|$, з якої, в свою чергу, випливає нерівність $\rho (G)\geq \nu (G)$. Якщо в графі існує досконале парування, то $\rho (G)=\nu (G)=|V|/2$.

Також для графа без ізольованих вершин виконується нерівність $\rho (G)\geq \alpha (G)$, де $\alpha (G)$ — число незалежності графа $G$. У двочастковомі графі $G$, внаслідок теореми Кеніга, $\rho (G)=\alpha (G)$.

Посилання

• László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.