Match szám

Egy gráf illesztési száma a benne lévő legnagyobb egyezés mérete . $G$

Egy tetszőleges gráfban a megfelelő szám az Edmonds-algoritmus segítségével időben megkereshető . Micali és Vazirani olyan algoritmust mutatott be, amely időben a legnagyobb egyezést hozza létre . Egy másik (randomizált) algoritmus, amelyet Mucha és Sankowski fejlesztett ki, a gyors mátrixszorzaton alapul , összetettséget ad . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$ $O(V^{{2,376}})$

Egy izolált csúcsok nélküli gráfban az illesztési szám a második Gallai-azonossággal : , az élfedési számhoz kapcsolódik , ami viszont az egyenlőtlenséget jelenti . Ha van tökéletes egyezés a grafikonon, akkor . $G=(V,E)$ $\nu (G)$ $\rho (G)$ $\nu (G)+\rho (G)=|V|$ $\nu (G)\leq \rho (G)$ $\nu (G)=\rho (G)=|V|/2$

Minden gráfban igaz az egyenlőtlenség is , ahol a gráf csúcsának a száma . Kétrészes gráfban a Koenig - tétel miatt . $G$ $\nu (G)\leq \tau (G)$ $\tau (G)$ $G$ $G$ $\nu (G)=\tau (G)$

Linkek

Lovász László, Michael D. Plummer. Párosítási elmélet. - Észak-Hollandia, 1986. - ISBN 0-444-87916-1 .