63
правки
Изменения
→Алгоритм
Пусть у нас есть матрица <tex>X</tex> размером <tex>n \times n</tex>, где <tex>n = |V_1| = |V_2|</tex>. Пусть <tex>X_{ij} = x_{ij}</tex> если <tex>(i,j) \in E</tex>, <tex>0</tex> иначе. Пусть детерминант матрицы <tex>det(X) = \sum\nolimits_{\sigma \in S_n} (-1)^{sign(\sigma)} \prod\limits_{i=1}^n X_{i,\sigma(i)}</tex>. Где <tex>S_n</tex> это множество всех перестановок <tex>{1, 2, ..., n}</tex>. Каждая такая перестановка это возможное полное паросочетание. Тогда ясно что если <tex>det(X) \ne 0 \iff</tex> когда в <tex>G \: \exists</tex> полное паросочетание. Таким образом: в графе <tex>\exists</tex> полное паросочетание <tex>\iff det(X) \ne 0</tex>
Заметим две вещи. Первое: у полинома <tex>det(X)</tex> всего <tex>|E|</tex> переменных и общая??? степень не более <tex>n</tex>. Второе: хотя размер <tex>det(X)</tex> может быть экспоненциальным, для точно заданных значений <tex>x_{ij}</tex> cуществуют известные полиномиальные алгоритмы. (задача вычисления детерминанта <tex>\in NC^2</tex>)
Это ведет нас к алоритму, который называется рандомизированный алгоритм Ловаса. Сформулируем его: выберем случайные числа для <tex>x_{ij}</tex>. Если <tex>det(X) \ne 0</tex> значит говорим что в графе есть полное паросочетание, иначе говорим что нету. Основное преимущество этого алгоритма в том, что он может быть реализован с помощью рандомизированной <tex>NC</tex> схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.
