1

Тема: Максимальное паросочетание в произвольном графе

Недавно на сайте появилась статья о матрице Татта. Насколько я знаю, при помощи такого рандомизированного алгоритма можно не только проверять, существует ли полное паросочетание, а еще и находить размер максимального паросочетания, который равен рангу этой матрицы.

2

Re: Максимальное паросочетание в произвольном графе

Окей, мне вчера тоже на почту написали об этом.

Я видел этот факт в литературе (над доказательством ещё подумаю, пока неочевидно), но мне показалось, что искать этот ранг в рандомизированной матрице будет очень ненадежно (всё же одно дело - посчитать определитель всей матрицы и сравнить его с нулём, и совсем другое - использовать фактически множество значений миноров для нахождения ранга), поэтому я не включал это в статью. Но, похоже, на практике это тоже работает неплохо, поэтому это надо написать тоже.

Спасибо.

3

Re: Максимальное паросочетание в произвольном графе

Улучшил статью, - теперь сказано и про размер макс. парсоча (с наметками док-ва), и про нахождение самого паросочетания (хотя по-прежнему за не очень крутую асимптотику).

4

Re: Максимальное паросочетание в произвольном графе

Нахождение паросочетания можно ускорить до O(n^3) если использовать формулу Шермана-Моррисона (http://en.wikipedia.org/wiki/Sherman%E2 … on_formula)