Číslo nezávislosti

Číslo nezávislosti grafu je velikost největší nezávislé množiny vrcholů v grafu. $G$

Protože problém nezávislých množin je NP-úplný , neexistují žádné známé algoritmy pro určování čísla nezávislosti v libovolném grafu, které pracují v polynomiálním čase.

V každém grafu je číslo nezávislosti vztaženo k číslu pokrytí vrcholu první Gallaiovou identitou:, navíc doplněk největší nezávislé množiny vrcholů je nejmenší pokrytí vrcholu. Pomocí této skutečnosti lze v bipartitním grafu nalézt v polynomiálním čase, protože problém pokrytí nejmenších vrcholů v něm je redukován na nalezení největší shody . $G=(V,E)$ $\alpha (G)$ $\tau (G)$ $\alpha (G)+\tau (G)=|V|$ $G$ $\alpha (G)$

V grafu bez izolovaných vrcholů (vrcholy stupně 0) platí i nerovnost , kde je počet pokrytí hran grafu . V bipartitním grafu bez izolovaných vrcholů, díky Königově větě , . $G$ $\alpha (G)\leq \rho (G)$ $\rho (G)$ $G$ $G$ $\alpha (G)=\rho (G)$

Odkazy

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