En teoría de grafos , la matriz A de Tutte de un grafo G = ( V , E ) es una matriz que se usa para determinar la existencia de una coincidencia perfecta : es decir, un conjunto de aristas que incide con cada vértice exactamente una vez.
Si el conjunto de vértices es entonces la matriz de Tutte es una matriz A n × n con entradas
donde los x ij son indeterminados. El determinante de esta matriz de simetría sesgada es entonces un polinomio (en las variables x ij , i
La matriz de Tutte lleva el nombre de WT Tutte y es una generalización de la matriz de Edmonds para un gráfico bipartito equilibrado .
Referencias
- R. Motwani, P. Raghavan (1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge. pag. 167.
- Allen B. Tucker (2004). Manual de informática . Prensa CRC. pag. 12.19. ISBN 1-58488-360-X.
- WT Tutte (abril de 1947). "La factorización de gráficos lineales" (PDF) . J. London Math. Soc . 22 (2): 107-111. doi : 10.1112 / jlms / s1-22.2.107 . Consultado el 15 de junio de 2008 .