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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

Посилання[ред. | ред. код]