Numărul de acoperire a vârfurilor

Numărul de acoperire a vârfurilor graficului este dimensiunea celui mai mic înveliș de vârf din acesta. $G$

Deoarece problema acoperirii vârfurilor este NP-complet , atunci, din păcate, nu există algoritmi pentru determinarea numărului de acoperire a vârfurilor într-un grafic arbitrar care să funcționeze în timp polinomial.

În orice grafic , numărul de acoperire a vârfurilor este legat de numărul de independență prin prima identitate Gallai : , în plus, complementul celui mai mic înveliș de vârf este cel mai mare set independent de vârfuri. $G=(V,E)$ $\tau (G)$ $\alpha (G)$ $\alpha (G)+\tau (G)=|V|$

În orice grafic , inegalitatea este valabilă , unde este numărul de potrivire al graficului . Într -un graf bipartit , datorită teoremei lui Koenig , . Prin urmare, în graficele bipartite, problema determinării este rezolvată în timp polinomial. $G$ $\tau (G)\geq \nu (G)$ $\nu (G)$ $G$ $G$ $\tau (G)=\nu (G)$ $\tau (G)$

Link -uri

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