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> иначе. Пусть детерминант матрицы <tex>det(X) = \sum\nolimits_{\sigma \in S_n} (-1)^{sign(\sigma)} \prod\limits_{i=1}^n X_{i,\sigma(i)}</tex>. Где <tex>S_n</tex> это множество всех перестановок <tex>{1, 2, ..., n}</tex>. Каждая такая перестановка это возможное полное паросочетание. Тогда ясно что если <tex>det(X) \ne 0 \iff</tex> когда в <tex>G \: \exists</tex> полное паросочетание. Таким образом: в графе <tex>\exists</tex> полное паросочетание <tex>\iff det(X) \ne 0</tex>
