Matchnummer

Det matchande numret för en graf är storleken på den största matchningen i den. $G$

I en godtycklig graf kan det matchande numret hittas med Edmonds algoritm i tid . Micali och Vazirani visade en algoritm som bygger den största matchningen i tid . En annan (randomiserad) algoritm utvecklad av Mucha och Sankowski, baserad på den snabba matrisprodukten , ger komplexitet . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$ $O(V^{{2,376}})$

I en graf utan isolerade hörn är det matchande numret relaterat till kanttäckningsnumret med den andra Gallai-identiteten : , vilket i sin tur innebär olikheten . Om det finns en perfekt matchning i grafen, då . $G=(V,E)$ $\nu (G)$ $\rho (G)$ $\nu (G)+\rho (G)=|V|$ $\nu (G)\leq \rho (G)$ $\nu (G)=\rho (G)=|V|/2$

I vilken graf som helst är olikheten också sann , där är numret på grafens vertextäcke . I en tvådelad graf , på grund av Koenigs sats , . $G$ $\nu (G)\leq \tau (G)$ $\tau (G)$ $G$ $G$ $\nu (G)=\tau (G)$

Länkar

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