En teoría de grafos , la matriz de Tutte A de un grafo G = ( V , E ) es una matriz utilizada para determinar la existencia de un emparejamiento perfecto : 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 de n por n con entradas
donde las x ij son indeterminadas . El determinante de esta matriz antisimétrica es entonces un polinomio (en las variables x ij , i < j ): éste coincide con el cuadrado del pfaffiano de la matriz A y es distinto de cero (como polinomio) si y sólo si existe un emparejamiento perfecto. (Este polinomio no es el polinomio de Tutte de G .)
La matriz de Tutte recibe su nombre de WT Tutte y es una generalización de la matriz de Edmonds para un gráfico bipartito equilibrado .
