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