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

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

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

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

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

Див. також

• Число парування

Посилання

• Шаблон:Книга