Edmonds matrix
From Wikipedia, the free encyclopedia
In graph theory, the Edmonds matrix A of a bipartite graph G(U,V,E) with sets of vertices 
and 
is defined by
where the xij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(Aij) in the xij is not identically zero.
[edit] References
- R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press, p. 167.
.svg/30px-Encoder_Disc_(3-Bit).svg.png){kind=small}
