Numărul de independență

Numărul de independență al unui grafic este dimensiunea celui mai mare set independent de vârfuri din acesta. $G$

Deoarece problema mulțimii independente este NP-completă , nu există algoritmi cunoscuți pentru determinarea numărului de independență într-un grafic arbitrar care să funcționeze în timp polinomial.

În orice grafic , numărul de independență este legat de numărul de acoperire a vârfurilor prin prima identitate Gallai : , în plus, complementul celui mai mare set de vârfuri independent este cel mai mic acoperire de vârf. Folosind acest fapt, într-un graf bipartit poate fi găsit în timp polinomial, deoarece problema celui mai mic vârf de acoperire din acesta se reduce la găsirea celei mai mari potriviri . $G=(V,E)$ $\alpha (G)$ $\tau (G)$ $\alpha (G)+\tau (G)=|V|$ $G$ $\alpha (G)$

Într-un grafic fără vârfuri izolate (vârfurile de gradul 0), inegalitatea este valabilă și , unde este numărul de acoperire a muchiei graficului . Într -un graf bipartit fără vârfuri izolate, datorită Teoremei lui König , . $G$ $\alpha (G)\leq \rho (G)$ $\rho (G)$ $G$ $G$ $\alpha (G)=\rho (G)$

Link -uri

László Lovász, Michael D. Plummer. Teoria potrivirii. - Olanda de Nord, 1986. - ISBN 0-444-87916-1 .