Matriz de Edmonds

---

En teoría de grafos , la matriz de Edmonds de un grafo bipartito balanceado con conjuntos de vértices y está definida por ${\ Displaystyle A}$ ${\ Displaystyle G (U, V, E)}$${\ Displaystyle U = \ {u_ {1}, u_ {2}, \ dots, u_ {n} \}}$${\ Displaystyle V = \ {v_ {1}, v_ {2}, \ dots, v_ {n} \}}$

donde los x _ij son indeterminados . Una aplicación de la matriz de Edmonds de un gráfico bipartito es que el gráfico admite una correspondencia perfecta si y solo si el polinomio det ( A _ij ) en x _ij no es idénticamente cero. Además, el número de emparejamientos perfectos es igual al número de monomios en el polinomio det ( A ), y también es igual al permanente de . Además, el rango de es igual al tamaño de coincidencia máximo de .${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle G}$

La matriz de Edmonds lleva el nombre de Jack Edmonds . La matriz de Tutte es una generalización a gráficos no bipartitos.

---