Число парування

Число́ парува́ння графа $G$ — розмір найбільшого парування в ньому.

У довільному графі число парування можна знайти за допомогою алгоритму Едмондса за час $O(|E||V|^{2})$. Мікалі й Вазірані показали алгоритм, який будує найбільше парування за час $O(|E||V|^{1/2})$. Інший (рандомізований) алгоритм, розроблений Муча і Санковським (Mucha, Sankowski), заснований на швидкому множенні матриць, дає складність $O(V^{2.376})$.

У графі $G=(V,E)$ без ізольованих вершин число парування $\nu (G)$ пов'язане з числом реберного покриття $\rho (G)$ другою тотожністю Галлаї: $\nu (G)+\rho (G)=|V|$, з якої, в свою чергу, випливає нерівність $\nu (G)\leq \rho (G)$. Якщо в графі існує досконале парування, то $\nu (G)=\rho (G)=|V|/2$.

У будь-якому графі $G$ також виконується нерівність $\nu (G)\leq \tau (G)$, де $\tau (G)$ — число вершинного покриття графа $G$. У двочастковому графі $G$, внаслідок теореми Кеніга, $\nu (G)=\tau (G)$.

Посилання

• László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.