Číslo zápasu

Shodné číslo grafu je velikost největší shody v grafu. $G$

V libovolném grafu lze najít odpovídající číslo pomocí Edmondsova algoritmu v čase . Micali a Vazirani ukázali algoritmus, který vytváří největší shodu v čase . Další (randomizovaný) algoritmus vyvinutý Muchou a Sankowskim, založený na rychlém maticovém produktu , poskytuje složitost . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$ $O(V^{{2,376}})$

V grafu bez izolovaných vrcholů je odpovídající číslo vztaženo k číslu pokrytí hrany druhou Gallaiovou identitou : , což zase implikuje nerovnost . Pokud je v grafu dokonalá shoda, pak . $G=(V,E)$ $\nu (G)$ $\rho (G)$ $\nu (G)+\rho (G)=|V|$ $\nu (G)\leq \rho (G)$ $\nu (G)=\rho (G)=|V|/2$

V každém grafu platí také nerovnost , kde je číslo krytí vrcholu grafu . V bipartitním grafu je díky Koenigově větě . $G$ $\nu (G)\leq \tau (G)$ $\tau (G)$ $G$ $G$ $\nu (G)=\tau (G)$

Odkazy

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