Matrice de Tutte

En théorie des graphes, la matrice de Tutte d'un graphe $G=(V,E)$ 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 $V=\{1,\dots ,n\}$, alors la matrice de Tutte de $G$ est une matrice de taille $n\times n$ ayant pour coefficients :

$$A_{ij}={\begin{cases}x_{ij},&{\text{si }}(i,j)\in E{\text{ et }}i<j\\-x_{ij},&{\text{si }}(i,j)\in E{\text{ et }}i>j\\0&{\text{sinon.}}\end{cases}}$$

où $x_{ij}$ sont les indéterminées. Le déterminant de cette matrice antisymétrique est un polynôme (en les variables $x_{ij},\ i<j$) : il coïncide avec le déterminant pfaffien de $A$ 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 $G$).

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.