Numărul de potrivire

Numărul de potrivire al unui grafic este dimensiunea celei mai mari potriviri din acesta. $G$

Într-un grafic arbitrar, numărul potrivit poate fi găsit folosind algoritmul Edmonds în timp . Micali și Vazirani au arătat un algoritm care construiește cea mai mare potrivire în timp . Un alt algoritm (randomizat) dezvoltat de Mucha și Sankowski, bazat pe produsul matricei rapid , dă complexitate . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$ $O(V^{{2,376}})$

Într-un grafic fără vârfuri izolate, numărul de potrivire este legat de numărul de acoperire a muchiei prin a doua identitate Gallai : , care, la rândul său, implică inegalitatea . Dacă există o potrivire perfectă în grafic, atunci . $G=(V,E)$ $\nu (G)$ $\rho (G)$ $\nu (G)+\rho (G)=|V|$ $\nu (G)\leq \rho (G)$ $\nu (G)=\rho (G)=|V|/2$

În orice grafic , inegalitatea este de asemenea adevărată , unde este numărul acoperirii vârfurilor graficului . Într -un graf bipartit , datorită teoremei lui Koenig , . $G$ $\nu (G)\leq \tau (G)$ $\tau (G)$ $G$ $G$ $\nu (G)=\tau (G)$

Link -uri

László Lovász, Michael D. Plummer. Teoria potrivirii. - Olanda de Nord, 1986. - ISBN 0-444-87916-1 .