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

розмір найменшого вершинного покриття графа

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

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

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

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

Посилання

ред.