Match nummer

Det matchende nummer på en graf er størrelsen af det største match i den. $G$

I en vilkårlig graf kan det matchende nummer findes ved hjælp af Edmonds algoritme i tid . Micali og Vazirani viste en algoritme, der bygger den største matching i tid . En anden (randomiseret) algoritme udviklet af Mucha og Sankowski, baseret på det hurtige matrixprodukt , giver kompleksitet . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$ $O(V^{{2,376}})$

I en graf uden isolerede hjørner er det matchende nummer relateret til kantdækningsnummeret med den anden Gallai-identitet : , hvilket igen indebærer uligheden . Hvis der er et perfekt match i grafen, så . $G=(V,E)$ $\nu (G)$ $\rho (G)$ $\nu (G)+\rho (G)=|V|$ $\nu (G)\leq \rho (G)$ $\nu (G)=\rho (G)=|V|/2$

I enhver graf er uligheden også sand , hvor er nummeret på grafens toppunkt . I en todelt graf , på grund af Koenigs sætning , . $G$ $\nu (G)\leq \tau (G)$ $\tau (G)$ $G$ $G$ $\nu (G)=\tau (G)$

Match nummer

Links