Independence nummer

Oberoendenumret för en graf är storleken på den största oberoende uppsättningen av hörn i den. $G$

Eftersom det oberoende uppsättningsproblemet är NP-komplett finns det inga kända algoritmer för att bestämma oberoendetalet i en godtycklig graf som fungerar i polynomtid.

I vilken graf som helst är oberoende numret relaterat till vertextäckningsnumret med den första Gallai-identiteten : dessutom är komplementet av den största oberoende vertexuppsättningen det minsta vertextäcket. Med hjälp av detta faktum kan i en tvådelad graf hittas i polynomtid, eftersom problemet med det minsta vertextäcket i det reduceras till att hitta den största matchningen . $G=(V,E)$ $\alpha (G)$ $\tau (G)$ $\alpha (G)+\tau (G)=|V|$ $G$ $\alpha (G)$

I en graf utan isolerade hörn (hörn av grad 0) gäller även olikheten , där är antalet kanttäckningar av grafen . I en tvådelad graf utan isolerade hörn, på grund av Königs sats , . $G$ $\alpha (G)\leq \rho (G)$ $\rho (G)$ $G$ $G$ $\alpha (G)=\rho (G)$

Länkar

László Lovász, Michael D. Plummer. Matchande teori. - North-Holland, 1986. - ISBN 0-444-87916-1 .