Vertex-peiton määrä

Graafin kärjen peitteen numero on siinä olevan pienimmän kärjen peitteen koko . $G$

Koska kärjenpeitto-ongelma on NP-täydellinen , niin valitettavasti ei ole olemassa polynomiajassa toimivia algoritmeja mielivaltaisen graafin kärkipeitteen lukumäärän määrittämiseksi.

Missä tahansa graafissa kärjen peitteen numero on suhteessa riippumattomuusnumeroon ensimmäisellä Gallai-identiteetillä : lisäksi pienimmän kärjen peitteen komplementti on suurin riippumaton kärkijoukko. $G=(V,E)$ $\tau (G)$ $\alpha (G)$ $\alpha (G)+\tau (G)=|V|$

Missä tahansa graafissa pätee myös epäyhtälö , jossa on graafin vastaavuusluku . Kaksiosaisessa graafissa Koenigin lauseesta johtuen . _ Siksi kaksiosaisissa kaavioissa määritysongelma ratkaistaan polynomiajassa. $G$ $\tau (G)\geq \nu (G)$ ${\näyttötyyli \nu (G)}$ $G$ $G$ $\tau (G)=\nu (G)$ $\tau (G)$

Linkit

László Lovász, Michael D. Plummer. Vastaamisen teoria. - Pohjois-Hollanti, 1986. - ISBN 0-444-87916-1 .