Участник:Zerogerc

Примеры рандомизированных алгоритмов

Проверка двудольного графа на существование в нем полного паросочетания

Задача

[math]let G = (V_1, V_2, E)[/math] — двудольный граф, где [math]|V_1|=|V_2|[/math] и[math]E \subseteq V_1 \times V_2[/math], тогда полным паросочетанием называется [math]E' \subseteq E[/math] такое что каждая вершина является концом ровно одного ребра из [math]E'[/math].

Алгоритм

Пусть у нас есть матрица [math]X[/math] размером [math]n \times n[/math], где [math]n = |V_1| = |V_2|[/math]. Пусть [math]X_{ij} = x_{ij}[/math] если [math](i,j) \in E[/math], [math]0[/math] иначе. Пусть детерминант матрицы [math]det(X) = \sum\nolimits_{\sigma \in S_n} (-1)^{sign(\sigma)} \prod\limits_{i=1}^n X_{i,\sigma(i)}[/math]. Где [math]S_n[/math] это множество всех перестановок [math]{1, 2, ..., n}[/math]. Каждая такая перестановка это возможное полное паросочетание. Тогда ясно что если [math]det(X) \ne 0 \iff[/math] когда в [math]G \: \exists[/math] полное паросочетание. Таким образом: в графе [math]\exists[/math] полное паросочетание [math]\iff det(X) \ne 0[/math]

Заметим две вещи. Первое: у полинома [math]det(X)[/math] всего [math]|E|[/math] переменных и общая??? степень не более [math]n[/math]. Второе: хотя размер [math]det(X)[/math] может быть экспоненциальным, для точно заданных значений [math]x_{ij}[/math] cуществуют известные полиномиальные алгоритмы. (задача вычисления детерминанта [math]\in NC^2[/math])

Это ведет нас к алоритму, который называется рандомизированный алгоритм Ловаса. Сформулируем его: выберем случайные числа для [math]x_{ij}[/math]. Если [math]det(X) \ne 0[/math] значит говорим что в графе есть полное паросочетание, иначе говорим что нету. Основное преимущество этого алгоритма в том, что он может быть реализован с помощью рандомизированной [math]NC[/math] схемы, а это значит что он может быть эффективно реализован используя параллельные вычисления.