Počet žeber

Číslo pokrytí hran grafu je velikost nejmenšího pokrytí hran v grafu. $G$

Pokud má graf izolované vrcholy (tedy vrcholy se stupněm 0), není zde žádné krytí hran, a proto není definován počet krytí hran. $G$

V libovolném grafu bez izolovaných vrcholů lze číslo pokrytí hran najít pomocí Edmondsova algoritmu pro párování v čase a poté přidáním hran pokrývajících vrcholy, které nejsou nasyceny největším párováním. $O(|E||V|^{2})$

V grafu bez izolovaných vrcholů souvisí krycí číslo hrany se shodným číslem druhou Gallaiovou identitou : , což zase implikuje nerovnost . Pokud je v grafu dokonalá shoda, pak . $G=(V,E)$ $\rho (G)$ $\nu (G)$ $\nu (G)+\rho (G)=|V|$ $\rho (G)\geq \nu (G)$ $\rho (G)=\nu (G)=|V|/2$

Také pro graf bez izolovaných vrcholů platí nerovnost , kde je číslo nezávislosti grafu . V bipartitním grafu je díky Koenigově větě . $\rho (G)\geq \alpha (G)$ $\alpha (G)$ $G$ $G$ $\rho (G)=\alpha (G)$

Odkazy

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