Matriz de Tutte

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 ${\displaystyle V=\{1,2,\puntos ,n\}}$

${\displaystyle A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{si}}\;(i,j)\en E{\mbox{ y }}i<j\\-x_{ji}\;\;{\mbox{si}}\;(i,j)\en E{\mbox{ y }}i>j\\0\;\;\;\;{\mbox{en caso contrario}}\end{cases}}}$

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 .

• R. Motwani, P. Raghavan (1995). Algoritmos aleatorios . Cambridge University Press. pág. 167.
• Allen B. Tucker (2004). Manual de Ciencias de la Computación . CRC Press. pág. 12.19. ISBN 1-58488-360-X.
• WT Tutte (abril de 1947). "La factorización de grafos 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 .