Matrice de Tutte

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

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

• Portail des mathématiques