Изменения

Пусть у нас есть матрица <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>