63
правки
Изменения
м
→Алгоритм
Заметим две вещи. Первое: у полинома <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> схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.
