Namespaces
Variants
Actions

Difference between revisions of "Edmonds matrix"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Edmonds matrix)
 
m (→‎References: isbn link)
 
Line 13: Line 13:
  
 
==References==
 
==References==
* Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) ISBN 978-0-521-47465-8 {{ZBL|0849.68039}}
+
* Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) {{ISBN|978-0-521-47465-8}} {{ZBL|0849.68039}}
* Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) ISBN 158488360X
+
* Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) {{ISBN|158488360X}}

Latest revision as of 07:29, 14 November 2023

2020 Mathematics Subject Classification: Primary: 05C50 Secondary: 05C70 [MSN][ZBL]

In graph theory, the Edmonds matrix $A$ of a balanced bipartite graph $G = (V,E)$ is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. Suppose that the vertex set $V = A \cup B$ where $A = \{a_1,\ldots,a_n\}$ and $B = \{b_1,\ldots,b_n\}$ .

The Edmonds matrix is an $n \times n$ matrix $A$ with entries $$ A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(a_i,b_j) \in E \\ 0\;\;\;\;\mbox{otherwise} \end{cases} $$ where the $x_{ij}$ are indeterminates. The determinant of this matrix is then a polynomial in the variables $x_{ij}$ and is non-zero (as a polynomial) if and only if a perfect matching exists.

The Tutte matrix is a generalisation of the Edmonds matrix to a general graph.

References

  • Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) ISBN 978-0-521-47465-8 Zbl 0849.68039
  • Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) ISBN 158488360X
How to Cite This Entry:
Edmonds matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Edmonds_matrix&oldid=54444