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

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

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

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

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

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

Посилання

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