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

Ссылки

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