Участник: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]