Число́ незале́жності або число́ вну́трішньої щі́льності графа — це розмір найбільшої незалежної множини вершин у ньому.
Оскільки задача про незалежну множину є NP-повною, то невідомі алгоритми визначення числа незалежності в довільному графі, що працюють за поліноміальний час.
У будь-якому графі число незалежності пов'язане з числом вершинного покриття першою (тотожністю Галлаї): , більш того, доповнення до найбільшої незалежної множини вершин є найменшим вершинним покриттям. Використовуючи цей факт, у двочастковому графі можна знайти за поліноміальний час, оскільки задача про найменше вершинне покриття в ньому зводиться до пошуку найбільшого парування.
У графі , в якому відсутні ізольовані вершини (вершини степеня 0), також виконується нерівність , де — (число реберного покриття) графа . У двочастковому графі без ізольованих вершин, унаслідок (теореми Кеніга), .
Див. також
- (Число парування)
Посилання
- László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет