Русская Википедия:Число паросочетания

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Ссылки

• Шаблон:Книга