63
правки
Изменения
→Проверка двудольного графа на существование в нем полного паросочетания
===Проверка двудольного графа на существование в нем полного паросочетания===
====Задача====<tex>let G = (V_1, V_2, E)</tex> {{---}} двудольный граф, где <tex>|V_1|=|V_2|</tex> и<tex>E \subseteq V_1 \times V_2</tex>, тогда полным паросочетанием называется <tex>E' \subseteq E</tex> такое что каждая вершина является концом ровно одного ребра из <tex>E'</tex>.====Алгоритм====Пусть у нас есть матрица <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> иначе.
