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

Число паросочетания графа ${\displaystyle G}$ — размер наибольшего паросочетания в нём.

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

В графе ${\displaystyle G=(V,E)}$ без изолированных вершин число паросочетания ${\displaystyle \nu (G)}$ связано с числом рёберного покрытия ${\displaystyle \rho (G)}$ вторым тождеством Галлаи: ${\displaystyle \nu (G)+\rho (G)=|V|}$, из которого, в свою очередь, следует неравенство ${\displaystyle \nu (G)\leq \rho (G)}$. Если в графе существует совершенное паросочетание, то ${\displaystyle \nu (G)=\rho (G)=|V|/2}$.

В любом графе ${\displaystyle G}$ также справедливо неравенство ${\displaystyle \nu (G)\leq \tau (G)}$, где ${\displaystyle \tau (G)}$ — число вершинного покрытия графа ${\displaystyle G}$. В двудольном графе ${\displaystyle G}$, вследствие Теоремы Кёнига, ${\displaystyle \nu (G)=\tau (G)}$.

Для любого неориентированного графа ${\displaystyle G}$ без петель и кратных рёбер справедливо неравенство ${\displaystyle \nu (G)\geq {\frac {m}{2(n-1)}}}$, где m и n - число рёбер и вершин графа соответственно.

Ссылки

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