title: Matrice de Tutte
text: # 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.
  
  