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{array}{cc}{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{array}$$

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.