A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
In graph theory, the Edmonds matrix of a balanced bipartite graph 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. 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 . In addition, rank of is equal to the maximum matching size of .
The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs.
References
- R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167. ISBN 9780521474658.
- Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.
>Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.