Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité.
L'importance de ce polynôme provient des informations qu'il contient sur le graphe . Étudié au départ dans le cadre de la théorie algébrique des graphes comme une généralisation des problèmes d'énumération liés à la coloration de graphes, il contient diverses spécialisations à d'autres disciplines, comme le polynôme de Jones en théorie des nœuds, les fonctions de partitions liées au en physique statistique, le polynôme énumérateur des poids en théorie des codes, le polynôme de fiabilité en théorie des réseaux. Tous peuvent être exprimés comme des spécialisations du polynôme de Tutte. Il est aussi à la source de divers problèmes algorithmiques en informatique théorique. L'interprétation combinatoire des polynômes de Tutte est en étroite relation avec l’énumération d'objets combinatoires par des méthodes de langages formels et séries formelles non commutatives présente une synthèse.
Les polynômes de Tutte ont plusieurs nom et définitions équivalents. Un polynôme de Tutte est équivalent au rang polynomial de Whitney, au polynôme dichromatique de Tutte et au random cluster model de Fortuin–Kasteleyn par des transformations simples. C'est essentiellement une série génératrice comptant les ensembles d'arêtes d'une taille de composantes connexes donnés, avec une généralisation naturelle aux matroïdes. C'est également l'invariant de graphes le plus général définissable par une récurrence de type suppression-contraction. Plusieurs livres de théorie des graphes ou de matroïdes consacrent des chapitres entiers aux polynômes de Tutte.... vignette|upright=2|Le polynôme est le polynôme de Tutte du graphe taureau. La ligne rouge indique l'intersection avec le plan , équivalent au polynôme chromatique.
Définitions et exemples Définitions équivalentes Soit un graphe non orienté, avec ensemble de sommets et ensemble d'arêtes . Pour , on note le graphe partiel qui a les mêmes sommets que , et ses arêtes dans .
Definition.- Le polynôme de Tutte d'un graphe est le polynôme défini par :
,
où est le nombre de composantes connexes du graphe . L'exposant du deuxième facteur est le nombre cyclomatique de .
On peut donner une formulation légèrement différente de la même définition en posant , où est le rang de Whitney du graphe . La fonction génératrice des rangs de Whitney est définie par :
.
Les deux fonctions sont équivalentes par un simple changement de variables. On a en effet :
.
Le polynôme dichromatique de Tutte résulte d'une autre transformation simple. On a :
.
Définition originale.- La définition originale de de Tutte est équivalente, mais moins facile à formuler. Pour un graphe connexe , on a
où est le nombre d'arbres couvrants d'« activité interne » et d' « activité externe » La définition de Tutte est comme suit. On suppose les arêtes du graphe totalement ordonnées. Une arête externe (interne) d’un arbre couvrant donné est active si elle est minimale dans son cycle (cocycle) fondamental. Lactivité interne (ou externe) est le nombre d'arêtes internes ou externes actives. Les ensembles d'arêtes internes ou externes actives d’un arbre couvrant dépendent de l’ordre total choisi, mais la somme de leurs nombres, sur les arbres couvrants, est indépendante de l’ordre choisi..
Contraction-suppression.- Une troisième définition est par récurrence sur la suppression d'arêtes. La contraction d'arête d'un graphe produit le graphe obtenu en fusionnant les sommets et et en supprimant l'arête . On note le graphe où l'on a seulement supprimé l'arête , sans fusionner ses deux extrémités. Le polynôme de Tutte est défini par récurrence par
selon que est boucle un isthme, ou ni l'un ni l'autre, avec la condition initiale
si ne contient pas d'arête.
Le « random cluster model » de la mécanique statistique dû à fournit encore une autre définition équivalente. : Le polynôme
est lié à par la transformation . :
Propriétés
Le polynôme de Tutte se factorise pour les composantes connexes : Si est l'union disjointe de graphes et , alors .
Deux graphes isomorphes ont même polynôme de Tutte, mais la réciproque est fausse. Par exemple, le polynôme de Tutte de toute forêt à arêtes est .
Si est un graphe planaire et si dénote son graphe dual, alors
.
En particulier, le polynôme chromatique d'un graphe planaire est le polynôme de flot de son dual.
Exemples
Les figures illustrent deux façons de calculer le polynôme de Tutte d'un petit graphe à 4 sommets et 4 arêtes : soit par la récurrence de contraction-suppression, soit par énumération des arbres couvrants.
Un polynôme de Tutte peut être donné sous forme de table, en présentant dans un tableau le coefficient de en ligne et colonne . Par exemple, le polynôme de Tutte du graphe de Petersen, qui est :
est donné par la table suivante :
{|class="wikitable" | 0 ||36|| 84|| 75|| 35|| 9|| 1 |- | 36 ||168 || 171 || 65 || 10 |- |120 || 240 || 105 || 15 |- |180 || 170 || 30 |- |170 || 70
|114 || 12 |- | 56 |- | 21
| 6 |- | 1
Un autre exemple, est le polynôme de Tutte du graphe octaédrique et :
Note historique Le polynôme a été introduit par W. T. Tutte dans son article de 1954, « A contribution to the theory of chromatic polynomials » . L'intérêt de Tutte pour la formule de contraction-suppression remonte à ses études undergraduate au Trinity College de Cambridge, motivé par les et les arbres couvrants. Il a utilisé souvent la formule dans ses recherches et se demandait « s'il existait d'autres invariants de graphes intéressants, aussi invariants par isomorphisme, avec des formules semblables ».. Ronald M. Foster avait déjà observé que le polynôme chromatique était de cette nature, et Tutte commençait à en découvrir d'autres. Il appelait au début W-function, et V-function dans le cas de fonctions multiplicatives sur les composantes connexes, les invariants de graphes vérifiant la formule de contraction-suppression. Tutte écrit : « En jouant avec mes W-functions j'ai obtenu un polynôme en deux variables dont on peut déduire soit le polynôme chromatique, soit le polynôme de flots, en annulant l'une ou l'autre des variables et en ajustant les signes » Tutte appelle cette fonction la dichromate, parce qu'il la concevait comme une généralisation du polynôme chromatique à deux variables mais elle est maintenant appelée polynôme de Tutte. Comme dit Tutte : « Ce n'est pas correct envers Hassler Whitney qui connaissait et utilisait ces coefficients analogues sans leur accoler deux variables ». Il y a une « confusion notable »Expression de Welsh. entre les termes « dichromate » et « dichromatic polynomial », introduit par Tutte dans un autre article, et qui n'en diffère que légèrement. La généralisation des polynômes de Tutte aux matroïdes a été publié en premier par Crapo, même si elle figure déjà dans la thèse de Tutte..
Indépendamment des recherches en théorie algébrique des graphes, Potts a commencé l'étude des fonctions de partition de certains modèles de mécanique statistique en 1952. Le travail de Fortuin et Kasteleyn. sur les , est une généralisation du modèle de Potts, et fournit une expression unifiée qui montre leur relation avec les polynômes de Tutte.
Spécialisations En faisant varier les valeurs de , les polynômes de Tutte prennent des formes qui ont déjà été étudiées pour elles-mêmes dans divers domaines des mathématiques ou de physique. L'un des attraits des polynômes de Tutte réside dans leur propriété à fournir un cadre unifié pour l'analyse de ces quantités.
Polynôme chromatique
Pour , le polynôme de Tutte se spécialises en le polynôme chromatique :
où est le nombre de composantes connexes de .
Pour des valeurs entières de , la valeur du polynôme chromatique est égale au nombre de colorations du graphe en utilisant couleurs. Clairement ne dépend pas de l’ensemble de couleurs. Ce qui est moins clair, c'est que c'est la valeur en d'un polynôme à coefficients entiers. Pour voir cela, on observe que : si G a n sommets et pas d'arêtes, alors . si G contient une boucle, alors . si e est une arête qui n'est pas une boucle, alors
Ces trois conditions permettent de calculer en appliquant une suite de contractions-suppressions, mais elles ne garantissent pas que des séquences différentes de suppressions et contractions conduisent au même résultat ; ceci provient du fait que compte des propriétés combinatoires, indépendamment de la récurrence. En particulier,
donne le nombre d'orientations acycliques du graphe.
Polynôme de Jones
Sur l'hyperbole , le polynôme de Tutte d'un graphe planaire se spécialise en le polynôme de Jones d'un nœud alternant associé obtenu via la construction du graphe médial. Louis Kauffman a proposé une généralisation du polynôme de Tutte pour les , ce qui donne via la construction médial un invariant de nœud qui se spécialise en le polynôme de Jones ainsi qu'en le de Kauffman.
Valeur en des points particuliers
(2,1) compte le nombre de forêts, c'est-à-dire le nombre des sous-ensembles d'arêtes sans cycle.
(1,1) compte le nombre de forêts couvrantes (c'est le nombre d'ensembles d'arêtes sans cycle et qui ont même nombre de composants connexes que G). Si le graphe est connexe, compte le nombre d'arbres couvrants.
(1,2) compte le nombre de sous-graphes couvrants (ensemble d'arêtes qui ont même nombre de composantes connexes que G).
(2,0 ) compte le nombre d' de G...
(0,2) compte le nombre d'orientations fortement connexes de G..
(0,−2) Si G est un graphe 4-régulier, alors
compte le nombre d'orientations eulériennes de G. Ici, est le nombre de composantes connexes de G.
(3,3) Si G est un graphe grille de paramètres , alors compte le nombre de manière de paver un rectangle de largeur 4m et de hauteur 4n avec des tétrominos. donnent des interprétations combintoires du polynôme de Tutte en de nombreux autres points..
Si G est un graphe planaire, alors est égal à la somme des partitions eulériennes pondérées du graphe médial de G, où le poids d'une orientation est 2 à la puissance le nombre de points selle de cette orientation (c'est-à-dire le nombre de sommets où l'orientation des arêtes incidentes est cycliquement « in, out, in out »)..
Modèles de Potts et d'Ising
On considère l'hyperbole définie par :
.
Sur cette hyperbole, le polynôme de Tutte se spécialise en la fonction de partition du modèle d'Ising étudiée en physique statistique. Plus précisément, le long de l'hyperbole ces deux fonctions sont liées par l'équation. :
Le lien avec l'hyperbole vient de ce que
pour tout nombre complexe .
Plus généralement, si on définit, pour tout entier q, l'hyperbole :
,
le polynôme de Tutte se spécialise en la fonction de partition du à q états. Diverses quantités physiques analysées dans le contexte du modèle de Potts se transposent en des parties spécifiques de .
+ Correspondances entre le modèle de Potts et le plan de Tutte. modèle de Potts polynôme de Tutte Ferromagnétisme Branche positive de Antiferromagnétisme Branche négative de avec Haute température Asymptote de pour Basse temperature ferromagnétiqueBranche positive de asymptotique en Température nulle antiferromagnetique q-coloration du graphe, c'est-à-dire .
Polynôme de flot