Число паросочетания

Число паросочетания графа $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.