Matrice de Tutte
En théorie des graphes, la matrice de Tutte d'un graphe est une matrice utilisée pour déterminer l'existence d'un couplage parfait, soit d'un ensemble d'arêtes incidentes à chaque sommet exactement une fois.
Si l'ensemble des sommets est , alors la matrice de Tutte de est une matrice de taille ayant pour coefficients :
où sont les indéterminées. Le déterminant de cette matrice antisymétrique est un polynôme (en les variables ) : il coïncide avec le déterminant pfaffien de et est non-identiquement nul si et seulement si un couplage parfait existe. (Ce polynôme ne doit pas être confondu avec le polynôme de Tutte de ).
La nom matrice de Tutte provient du mathématicien W. T. Tutte, et est la généralisation de la matrice d'Edmonds pour les graphes bipartis équilibrés.
Portail des mathématiques