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

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

В произвольном графе число паросочетания может быть найдено с помощью алгоритма Эдмондса за время . Микали и Вазирани показали алгоритм, который строит наибольшее паросочетание за время . Другой (рандомизированный) алгоритм, разработанный Муча и Санковским (Mucha, Sankowski), основанный на быстром произведении матриц, даёт сложность .

В графе без изолированных вершин число паросочетания связано с числом рёберного покрытия вторым тождеством Галлаи: , из которого, в свою очередь, следует неравенство . Если в графе существует совершенное паросочетание, то .

В любом графе также справедливо неравенство , где  — число вершинного покрытия графа . В двудольном графе , вследствие Теоремы Кёнига, .

Ссылки

  • László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.