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

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

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

У довільному графі без ізольованих вершин число реберного покриття можна знайти за допомогою алгоритму Едмондса для парувань за час і подальшого додавання ребер, що покривають не насичені найбільшим паруванням вершини.

У графі без ізольованих вершин число реберного покриття пов'язане з числом парування другою тотожністю Галлаї: , з якої, в свою чергу, випливає нерівність . Якщо в графі існує досконале парування, то .

Також для графа без ізольованих вершин виконується нерівність , де  число незалежності графа . У двочастковомі графі , внаслідок теореми Кеніга, .

Посилання

  • László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.