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

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

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

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

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