Число реберного покриття
Число́ ребе́рного покриття́ графа — розмір найменшого реберного покриття в ньому.
Якщо в графі є ізольовані вершини (тобто вершини зі степенем 0), то реберного покриття не існує, тому й число реберного покриття не визначене.
У довільному графі без ізольованих вершин число реберного покриття можна знайти за допомогою алгоритму Едмондса для парувань за час і подальшого додавання ребер, що покривають не насичені найбільшим паруванням вершини.
У графі без ізольованих вершин число реберного покриття пов'язане з числом парування другою тотожністю Галлаї: , з якої, в свою чергу, випливає нерівність . Якщо в графі існує досконале парування, то .
Також для графа без ізольованих вершин виконується нерівність , де — число незалежності графа . У двочастковомі графі , внаслідок теореми Кеніга, .
Посилання
- László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.