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

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

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

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

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

Ссылки

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