Edmonds matrix

In graph theory, the Edmonds matrix A of a balanced bipartite graph G(U, V, E) with sets of vertices U = \{u_1, u_2, \dots , u_n \} and V = \{v_1, v_2, \dots , v_n\} is defined by

 A_{ij} = \left\{ \begin{array}{ll}
   x_{ij} & (u_i, v_j) \in E \\
   0 & (u_i, v_j) \notin E
 \end{array}\right.

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. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of A. In addition, rank of A is equal to the maximum matching size of G.

The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs.

References

This article is issued from Wikipedia - version of the Monday, October 05, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.