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

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

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

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

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

Див. також

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

Посилання

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