Reminder: This post contains 1015 words
· 3 min read
· by Xianbin
This post will show how to detect and find a matching using matrix.
Definitions
Given a bipartite graph \(G=(L, R, E)\) with \(\lvert L\rvert = \lvert R \rvert = n\),
the Edmonds Matrix \(E(G)\) is defined as \(n\times n\) matrix of variables in the following.
\[\mathrm{E}_{i,j} =
\begin{cases}
0, & (i,j) \not \in E \text{ and } {i\in L, j\in R}\\
1, & (i,j)\in E \text{ and } {i\in L, j\in R}
\end{cases}\]
We know that the basics are always important.
For more about determinant, please read the post What is determinant.
\[\textup{Det}(\textbf{a}_1, \textbf{a}_2,\ldots, \textbf{a}_n) =
\sum_{(j_1,\ldots,j_n)\in \pi_n}\text{sgn}(j_1,\ldots,j_n) \prod_{i=1}^n v_{j_n i}\]
where \(\pi_n\) is a permutation.
Lovász’s Algorithm
\(\textbf{Theorem}\)[35] Let \(\textup{E}(G)\) be the Edmonds matrix of a bipartite graph \(G\). Then, \(\textup{E}(G)\) is non-zero iff \(G\) contains a perfect matching.
Wow! Cool! What a beautiful theory!
Karp, UPpfal, Wigderson Algorithm
Rabin and Vazirani Algorithm
Reference
[1] Tutte, William T. “The factorization of linear graphs.” Journal of the London Mathematical Society 1.2 (1947): 107-111.