Число незалежності

розмір незалежної множини вершин графа найбільшого розміру

Число́ незале́жності або число́ вну́трішньої щі́льності графа  — це розмір найбільшої незалежної множини вершин у ньому.

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

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

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

Див. такожРедагувати

ПосиланняРедагувати

  • László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.