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