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 :

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.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.