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

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

Оскільки (задача вершинного покриття) є NP-повною, то невідомі алгоритми визначення числа вершинного покриття в довільному графі, що працюють за поліноміальний час.

У будь-якому графі ${\displaystyle G=(V,E)}$ число вершинного покриття ${\displaystyle \tau (G)}$ пов'язане з числом незалежності ${\displaystyle \alpha (G)}$ першою тотожністю Галлаї: ${\displaystyle \alpha (G)+\tau (G)=|V|}$, більш того, доповнення до найменшого вершинного покриття є найбільшою незалежною множиною вершин.

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

Посилання

• László Lovász, ^[en]. Matching Theory. — North-Holland, 1986. — .