Voir la source de Polynôme de Tutte

{{Autre4|le polynôme de Tutte d'un graphe|le polynôme de Tutte d'un matroïde|Matroïde}}

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é]] <math>G</math> 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 <math>G</math>. É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 graphe]]s, 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 {{Lien|langue=en|trad=Potts model|fr=modèle de Potts}} 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ème algorithmique|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érie formelle|séries formelles]] non commutatives<ref name="Courtiel">{{harvsp|Courtiel|2014|p=}} présente une synthèse.</ref>

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ïde]]s. 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<ref>{{harvsp|id=Bollobas|Bollobás|1998|loc=chapter 10}}.</ref>{{,}}<ref>{{harvsp|Biggs|1993|loc=chapter 13}}.</ref>{{,}}<ref>{{harvsp|Godsil|Royle|2004|loc=chap. 15}}.</ref>.
[[Fichier:Tutte polynomial and chromatic polynomial of the Bull graph.jpg|vignette|upright=2|Le polynôme <math>x^4+x^3+x^2y</math> est le polynôme de Tutte du [[graphe taureau]]. La ligne rouge indique l'intersection avec le plan <math>y=0</math>, équivalent au polynôme chromatique.]]

== Définitions et exemples ==
=== Définitions équivalentes ===
Soit <math>G=(V,E)</math> un graphe non orienté, avec ensemble de sommets <math>V</math> et ensemble d'arêtes <math>E</math>. Pour <math>A\subseteq E</math>, on note <math>(V,A)</math> le [[graphe partiel]] qui a les mêmes sommets que <math>G</math>, et ses arêtes dans <math>A</math>.

'''Definition'''.- Le '''polynôme de Tutte''' d'un graphe <math>G=(V,E)</math> est le polynôme <math>T_G(x,y)</math> défini par :

:<math>T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}</math>,

où <math>k(A)</math> est le nombre de [[Graphe connexe|composantes connexes]] du graphe <math>(V,A)</math>. L'exposant <math>k(A)+|A|-|V|</math> du deuxième facteur est le [[Lexique de la théorie des graphes#C|nombre cyclomatique]] de <math>(V,A)</math>.

On peut donner une formulation légèrement différente de la même définition en posant
:<math>r(A)=|V|-k(A)</math>,
où <math>r(A)</math> est le rang de Whitney du graphe <math>(V,A)</math>. La '''fonction génératrice des rangs de Whitney''' est définie par :

:<math>R_G(u,v)=\sum\nolimits_{A\subseteq E} u^{r(E)-r(A)} v^{|A|-r(A)}</math>.

Les deux fonctions sont équivalentes par un simple changement de variables. On a en effet :

:<math>T_G(x,y)=R_G(x-1,y-1)</math>.

Le '''polynôme dichromatique''' <math>Q_G</math> de Tutte résulte d'une autre transformation simple. On a :

:<math>T_G(x,y)=(x-1)^{-k(G)} Q_G(x-1,y-1)</math>.

'''Définition originale'''.- La définition originale de <math>T_G</math> de Tutte est équivalente, mais moins facile à formuler. Pour un graphe connexe <math>G</math>, on a

:<math>T_G(x,y)=\sum\nolimits_{i,j} t_{ij} x^iy^j,</math>

où <math>t_{ij}</math> est le nombre d'[[arbre couvrant|arbres couvrants]] d'« activité interne » <math>i</math> et d' « activité interne » <math>j</math><ref>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. L{{'}}''activité 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.</ref>.

'''Contraction-suppression'''.- Une troisième définition est par récurrence sur la suppression d'arêtes. La [[contraction d'arête]] <math>uv</math> d'un graphe <math>G</math> produit le graphe <math>G/uv</math> obtenu en fusionnant les sommets <math>u</math> et <math>v</math> et en supprimant l'arête <math>uv</math>. On note <math>G - uv</math> le graphe où l'on a seulement supprimé l'arête <math>uv</math>, sans fusionner ses deux extrémités. Le polynôme de Tutte est défini par récurrence par

:<math>T_G(x,y)=\begin{cases} 
xT_{G/e}(x,y) &\text{si }\ e\ \text{ est un isthme},\\
yT_{G-e}(x,y) &\text{si }\ e\ \text{ est une boucle},\\
T_{G-e}(x,y)+T_{G/e}(x,y) &\text{sinon}.
\end{cases}</math>

selon que <math>e</math> est [[Boucle (théorie des graphes)|boucle]] un [[Isthme (théorie des graphes)|isthme]], ou ni l'un ni l'autre, avec la condition initiale

:<math>T_G=1</math> si <math>G</math> ne contient pas d'arête.

Le « '''random cluster model''' » de la [[mécanique statistique]] dû à {{harvsp|Fortuin|Kasteleyn|1972}} fournit encore une autre définition équivalente<ref>{{harvsp|Sokal|2005}}.</ref> : Le polynôme

:<math>Z_G(q,w)=\sum\nolimits_{F\subseteq E}q^{k(F)}w^{|F|}</math>

est lié à <math>T_G</math> par la transformation <ref>{{harvsp|Sokal|2005|loc=eq. (2.26)}}.</ref> :

:<math>T_G(x, y)=(x-1)^{-k(E)}(y-1)^{-|V|} \cdot Z_G\Big((x-1)(y-1),\; y-1\Big).</math>

=== Propriétés ===

Le polynôme de Tutte se factorise pour les composantes connexes : Si <math>G</math> est l'union disjointe de graphes <math>H</math> et <math>H'</math>, alors
: <math>T_G= T_H \cdot T_{H'}</math>.

Si <math>G</math> est un graphe planaire et si <math>G^*</math> dénote son [[graphe dual]], alors

: <math>T_G(x,y)= T_{G^*} (y,x)</math>.

En particulier, le [[polynôme chromatique]] d'un graphe planaire est le polynôme de flot de son dual.

=== Exemples ===
Deux graphes isomorphes ont même polynôme de Tutte, mais la réciproque est fausse. Par exemple, le polynôme de Tutte de tout arbre ayant <math>m</math> arêtes est <math>x^m</math>.

Un polynôme de Tutte peut être donné sous forme de table, en présentant dans un tableau le coefficient <math>t_{ij}</math> de <math>x^iy^j</math> en ligne <math>i</math> et colonne <math>j</math>. Par exemple, le polynôme de Tutte du [[graphe de Petersen]], qui est :

:<math>\begin{align}
36 x &+ 120 x^2 + 180 x^3 + 170x^4+114x^5 + 56x^6 +21 x^7 + 6x^8 + x^9 \\
&+ 36y +84 y^2 + 75 y^3 +35 y^4 + 9y^5+y^6 \\
&+ 168xy + 240x^2y +170x^3y +70 x^4y + 12x^5 y \\
&+ 171xy^2+105 x^2y^2 + 30x^3y^2 \\
&+ 65xy^3 +15x^2y^3 \\
&+10xy^4,
\end{align}</math>

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 :
:<math>\begin{align}
&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{
y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2} \\
&+25\,{x}^{2}+29\,{y}^{4}+15\,{y
}^{5}+5\,{y}^{6}+6\,{y}^{4}x \\
&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^
{3}+7\,{x}^{4}+{x}^{5}
\end{align}</math>

== Note historique ==
L'intérêt de [[William Tutte|W. T. Tutte]] pour la formule de contraction-suppression remonte à ses études ''undergraduate'' au [[Trinity College (Cambridge)|Trinity College]] de Cambridge, motivé par les {{Lien|langue=en|trad=Perfect rectangle|fr=rectangle parfait|texte=rectangles parfaits}} et les [[Arbre couvrant|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 »<ref name="Tutte-2004">{{harvsp|Tutte|2004}}.</ref>. [[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 [[Fonction multiplicative|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 »<ref name="Tutte-2004"/> 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 »<ref>Expression de Welsh.</ref> 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<ref name="Farr 2007">{{harvsp|Farr|2007}}.</ref>.

Indépendamment des recherches en théorie algébrique des graphes, Potts a commencé l'étude des [[Fonction de partition|fonctions de partition]] de certains modèles de [[mécanique statistique]] en 1952. Le travail de Fortuin et Kasteleyn<ref>{{harvsp|Fortuin|Kasteleyn|1972}}.</ref> sur les {{Lien|langue=en|trad=Random cluster model|fr=random cluster model|texte=random cluster model}}, 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<ref name="Farr 2007"/>.

== Spécialisations ==
En faisant varier les valeurs de <math>(x,y)</math>, 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 ===
{{Article détaillé|Polynôme chromatique}}
[[Image:Chromatic in the Tutte plane.jpg|vignette|droite|Le polynôme chromatique dans le plan de Tutte.]]

Pour <math>y=0</math>, le polynôme de Tutte se spécialises en le polynôme chromatique :

:<math>\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),</math>
où <math>k(G)</math> est le nombre de composantes connexes de <math>G</math>.

Pour des valeurs entières de <math>\lambda</math>, la valeur du polynôme chromatique <math>\chi_G(\lambda)</math> est égale au nombre de [[Coloration de graphe|colorations]] du graphe <math>G</math> en utilisant <math>\lambda</math> couleurs. Clairement <math>\chi_G(\lambda)</math> ne dépend pas de l’ensemble de couleurs. Ce qui est moins clair, c'est que c'est la valeur en <math>\lambda</math> d'un polynôme à coefficients entiers. Pour voir cela, on observe que :
# si ''G'' a ''n'' sommets et pas d'arêtes, alors <math>\chi_G(\lambda) = \lambda^n</math>.
# si ''G'' contient une boucle, alors <math>\chi_G(\lambda) = 0</math>.
# si ''e'' est une arête qui n'est pas une boucle, alors
::<math>\chi_G(\lambda) = \chi_{G\setminus e}(\lambda) - \chi_{G/e}(\lambda).</math>

Ces trois conditions permettent de calculer <math>\chi_G(\lambda)</math> 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 <math>\chi_G(\lambda)</math> compte des propriétés combinatoires, indépendamment de la récurrence. En particulier,

:<math>T_G(2,0) = (-1)^{|V|} \chi_G(-1)</math>

donne le nombre d'orientations acycliques du graphe.

=== Polynôme de Jones ===
{{Article détaillé|Polynôme de Jones}}
[[Image:Jones in the Tutte plane.jpg|vignette|droite|Polynômes de Jones dans le plan de Tutte.]]

Sur l'hyperbole <math>xy=1</math>, le polynôme de Tutte d'un graphe planaire se spécialise en le [[polynôme de Jones]] d'un nœud alternant associé.

=== Valeur en des points particuliers ===

==== (2,1) ====
<math>T_G(2,1)</math> compte le nombre de [[Arbre (théorie des graphes)|forêts]], c'est-à-dire le nombre des sous-ensembles d'arêtes sans cycle.

==== (1,1) ====
<math>T_G(1,1)</math> 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, <math>T_G(1,1)</math> compte le nombre d'arbres couvrants.

==== (1,2) ====
<math>T_G(1,2)</math> compte le nombre de sous-graphes couvrants (ensemble d'arêtes qui ont même nombre de composantes connexes que ''G'').

==== (2,0 ) ====
<math>T_G(2,0)</math> compte le nombre d'{{Lien|langue=en|trad=Acyclic orientation|fr=orientation acyclique|texte=orientations acycliques}} de ''G''<ref name="Welsh-1999">{{harvsp|Welsh|1999}}.</ref>{{,}}<ref name="Lass2001">{{harvsp|Lass|2001}}.</ref>.

==== (0,2) ====
<math>T_G(0,2)</math> compte le nombre d'[[Théorème de Robbins|orientations fortement connexes]] de ''G''<ref>{{harvsp|Las Vergnas|1980}}.</ref>.

==== (0,−2) ====
Si ''G'' est un [[Graphe régulier|graphe 4-régulier]], alors
:<math>(-1)^{|V|+k(G)}T_G(0,-2)</math>
compte le nombre d'[[Graphe eulérien|orientations eulériennes]] de ''G''. Ici, <math>k(G)</math> est le nombre de composantes connexes de ''G''<ref name="Welsh-1999"/>.

==== (3,3) ====
Si ''G'' est un [[graphe grille]] de paramètres <math>m\times n</math>, alors <math>2 T_G(3,3)</math> compte le nombre de manière de paver un rectangle de largeur 4''m'' et de hauteur 4''n'' avec des [[tétromino]]s<ref>{{harvsp|Korn|Pak|2004}}.</ref>{{,}}<ref>{{harvsp|Korn|Pak|2003}} donnent des interprétations combintoires du polynôme de Tutte en de nombreux autres points.</ref>.

Si ''G'' est un [[graphe planaire]], alors <math>2 T_G(3,3)</math> 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 »)<ref>{{harvsp|Las Vergnas|1988}}.</ref>.

=== Modèles de Potts et d'Ising ===
{{Article détaillé|contenu = Articles détaillés : [[Modèle d'Ising]] et {{Lien|langue=en|trad=Potts model|fr=modèle de Potts}}.}}
[[Image:Potts and Ising in the Tutte plane.jpg|vignette|droite|Les fonctions de partition pour le modèle d'Ising et pour les modèles de Potts à 3 et 4 états, dans le plan de Tutte..]]

On considère l'hyperbole <math>H_2</math> définie par :

:<math> H_2: \quad (x-1)(y-1)=2</math>.

Sur cette hyperbole, le polynôme de Tutte se spécialise en la fonction de partition <math>Z(\cdot),</math> du [[modèle d'Ising]] étudiée en [[physique statistique]]. Plus précisément, le long de l'hyperbole <math>H_2</math> ces deux fonctions sont liées par l'équation<ref>{{harvsp|Welsh|1993|p=62}}.</ref> :

:<math>Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)}  T_G \left (\coth \alpha, e^{2 \alpha} \right).</math>

Le lien avec l'hyperbole vient de ce que

:<math>(\coth \alpha - 1) \left(e^{2 \alpha} - 1 \right ) = 2</math>

pour tout nombre complexe <math>\alpha</math>.

Plus généralement, si on définit, pour tout entier ''q'', l'hyperbole :

:<math>H_q: \quad (x-1)(y-1)=q</math>,

le polynôme de Tutte se spécialise en la fonction de partition du {{Lien|langue=en|trad=Potts model|fr=modèle de Potts}} à ''q états.'' Diverses quantités physiques analysées dans le contexte du modèle de Potts se transposent en des parties spécifiques de ''<math>H_q</math>.''

{|class="wikitable" style="margin: 1em auto 1em auto"
|+ Correspondances entre le modèle de Potts et le plan de Tutte<ref>{{harvsp|Welsh|Merino|2000}}.</ref>
! modèle de Potts || polynôme de Tutte
|-
| [[Ferromagnétisme]]
|| Branche positive de <math>H_q</math>
|-
| [[Antiferromagnétisme]]
|| Branche négative de <math>H_q</math> avec <math>y>0</math>
|-
|  Haute température 
|| Asymptote de <math>H_q</math> pour <math>y=1</math>
|-
| Basse temperature ferromagnétique
||Branche positive de <math>H_q</math> asymptotique en <math>x=1</math>
|-
| Température nulle antiferromagnetique
|| [[Coloration de graphe|''q''-coloration du graphe]], c'est-à-dire <math>x=1-q, y=0</math>.
|}

=== Polynôme de flot ===
{{Article détaillé|contenu=Article détaillé : {{Lien|langue=en|fr=Nowhere-zero flow}}.}}

[[Image:Flow in the Tutte plane.jpg|vignette|droite|Le polynôme de flot dans le plan de Tutte.]]

Au point <math>x=0</math>, le polynôme de Tutte se spécialise en un polynôme appelé '''polynôme de flot''' et étudié en combinatoire. Pour un graphe non orienté connexe ''G'' et un entier ''k'', un ''k''-flot qui ne s'annule pas ({{Citation étrangère|langue=en|nowhere-zero flow}}) est une affectations de valeurs de « flot » <math>1,2,\dots,k-1</math> aux arcs d'une orientation arbitraire de ''G'' telle que le flot total entrant et le flot total sortant de chaque sommet sont égaux modulo ''k''. Le polynôme de flot <math>C_G(k)</math> compte le nombre de ces ''k''-flots. Cette valeur est étroitement liée au polynôme chromatique : en fait, si ''G'' est un [[graphe planaire]], le polynôme chromatique de ''G'' est équivalent au polynôme de flot de son [[graphe dual]] <math>G^*</math> par le théorème de Tutte suivant :
:<math>C_G(k)=k^{-1} \chi_{G^*}(k)</math>.
La connexion avec le polynôme de Tutte est donnée par :
: <math>C_G(k)= (-1)^{|E|+|V|+k(G)} T_G(0,1-k)</math>.

=== Polynôme de fiabilité ===
{{Article détaillé|contenu = Article détaillé : [[Graphe connexe|Connexité]].}}

[[Image:Reliability in the Tutte plane.jpg|vignette|droite|Le polynôme de fiabilité dans le plan de Tutte.]]

Pour <math>x=1</math>, le polynôme de Tutte se spécialise en le polynôme de fiabilité entre tous points étudié en [[théorie des réseaux]]. Pour un graphe connexe ''G'', on affecte une probabilité ''p'' à la suppression d'une arête, pour modéliser un réseau sujet à des pannes aléatoires d'arêtes. Le polynôme de fiabilité est le polynôme <math>R_G(p)</math> en ''p'' qui donne la probabilité qu'un couple de sommets de ''G'' reste connecté après des pannes sur les arêtes. Le lien avec le polynôme de Tutte est donné par :

:<math>R_G(p) = (1-p)^{|V|-k(G)} p^{|E|-|V|+k(G)} T_G (1, 1/p)</math>.

=== Polynôme dichromatique ===
Tutte a aussi défini une généralisation en deux variables des polynômes chromatiques voisine de ces derniers ; il les appelle '''polynômes dichromatiques'''. Pour un graphe <math>G=(V,E)</math>, c'est le polynôme

:<math>Q_G(u,v) = \sum\nolimits_{A \subseteq E} u^{k(A)} v^{|A|-|V|+k(A)},</math>

où <math>k(A)</math> est le nombre de [[graphe connexe|composantes connexes]] du graphe partiel <math>(V,A)</math>. Ce polynôme est relié au {{Citation étrangère|langue=en|corank-nullity polynomial}} par

:<math>Q_G(u,v) = u^{k(G)} \, R_G(u,v).</math>

Le polynôme dichromatique ne se généralise pas aux matroïdes parce <math>k(A)</math> n'est pas une propriété de matroïdes : des graphes avec même matroïde peuvent avoir un nombre différent de composantes connexes.



=== Polynôme de Martin ===
Le polynôme de Martin <math>m_{\vec{G}}(x)</math> d'un graphe orienté 4-régulier <math>\vec{G}</math> a été défini par Pierre Martin in 1977<ref>{{harvsp|Martin|1977}}.</ref>. Il a prouvé que si <math>G</math> est un graphe planaire et si <math>\vec{G}_m</math> est son [[graphe médial|graphe médial orienté]], alors

:<math>T_G(x,x) = m_{\vec{G}_m}(x).</math>

== Algorithmes ==

=== Suppression–contraction ===
[[Image:deletion-contraction.svg|vignette|droite|upright=2|L'algorithme de suppression–contraction applique au [[graphe diamant]]. Les arêtes rouges sont supprimées dans l'enfant gauche, contractées dans l'enfant droit. Le polynôme résultant est la somme des monômes des feuilles, <math>x^3+2x^2 +y^2+2xy+x+y</math>. Basé sur {{harv|Welsh|Merino|2000}}.]]

La formule de récurrence de suppression–contraction pour le polynôme de Tutte s'écrit :
: <math>T_G(x,y)= T_{G - e}(x,y) + T_{G/e}(x,y)</math>,
lorsque <math>e</math> n'est ni une boucle ni un isthme.
Ceci donne immédiatement un [[algorithme récursif]] pour le calcul du polynôme : choisir une arête quelconque ''e'' et appliquer la formule jusqu'à ce que toutes les arêtes restantes sont soit des boucles, soit des isthmes. Les cas restants sont alors faciles à évaluer.

À un facteur polynomial près, le temps de calcul ''t'' de cet algorithme peut être exprimé en fonction du nombre ''n'' de sommets et du nombre ''m'' d'arêtes du graphe,
:<math>t(n+m)= t(n+m-1) + t(n+m-2)</math> ;
cette relation est similaire à celle des [[Suite de Fibonacci|nombres de Fibonacci]] avec pour solution<ref>{{harvsp|Wilf|1986|p=46}}.</ref> :

:<math> t(n+m)= \left (\frac{1+\sqrt{5}}{2} \right )^{n+m} = O  (1.6180^{n+m} ).</math>

L'analyse peut être améliorée par un facteur polynomial en le nombre <math>\tau(G)</math> d'arbre couvrants du graphe donné<ref name="Sekine 1995">{{harvsp|Sekine|Imai|Tani|1995}}.</ref>. Pour des graphes creux, avec <math>m=O(n)</math> ce temps de calcul est en <math>O(\exp(n))</math>. Pour les graphes réguliers de degré ''k'', le nombre d'arbres couvrants peut être borné par

:<math>\tau(G) = O \left (\nu_k^n n^{-1} \log n \right ),</math> avec <math>\nu_k = \frac{(k-1)^{k-1}}{(k^2-2k)^{k/2-1}}</math>,

de sorte que l'algorithme de suppression–contraction s'exécute avec un facteur polynomial de cette borne. On a par exemple<ref>{{harvsp|Chung|Yau|1999}}, d'après {{harvsp|id=Bjorklund|Björklund|Husfeldt|Kaski|Koivisto|2008}}.</ref> : <math>\nu_5 \approx 4.4066.</math>

En pratique, un test d'[[isomorphisme de graphes]] est utilisé pour éviter des appels récursifs. Cette approche fonctionne bien pour des graphes que sont creux et qui présentent beaucoup de symétries ; l'efficacité dépend alors de l'heuristique utilisé pour choisir l'arête ''e''<ref name="Sekine 1995" />{{,}}<ref>{{harvsp|Haggard|Pearce|Royle|2010}}.</ref>{{,}}<ref>{{harvsp|Pearce|Haggard|Royle|2010}}.</ref>. Le choix de l'arête à supprimer s'avère primordial<ref>{{harvsp|Monagan|2012||p=}}.</ref>.

=== Élimination de Gauss-Jordan ===
Dans certains cas particuliers, le polynôme de Tutte peut être calculé en temps polynomial parce que l'[[élimination de Gauss-Jordan]] permet un calcul efficace des opérations matricielles comme le [[déterminant (mathématiques)|déterminant]] et le [[pfaffien]]. Ces algorithmes constituent eux-mêmes des résultats importants en théorie algébrique des graphes et en [[mécanique statistique]] .

<math>T_G(1,1)</math> est égal au nombre <math>\tau(G)</math> d'[[Arbre couvrant|arbres couvrants]] d'un graphe connexe. Cette valeur peut se calculer en temps polynomial en tant que [[déterminant (mathématiques)|déterminant]] de la sous-matrice principale maximale de la [[matrice laplacienne]] de ''G'', un résultat ancien de la théorie algébrique des graphes connu sous le nom de [[théorème de Kirchhoff]]. De façon similaire, la dimension de l'espace à deux cycles de <math>T_G(-1,-1)</math> peut être calculé par élimination de Gauss en temps polynomial.

Pour les graphes planaires, la fonction de partition du modèle d'Ising, c'est-à-dire le polynôme de Tutte sur l'hyperbole <math>H_2</math>, peut être exprimée comme un pfaffian et calculé de façon efficace au moyen de l'[[algorithme FKT]]. Cette idée a été développée par [[Michael Fisher|Fisher]], Kasteleyn et Temperley pour calculer le nombre de [[pavage]]s par des [[domino (pièce de jeu)|dominos]] pour paver un modèle en treillis plan.

=== Méthode de Monte-Carlo ===
En utilisant une [[méthode de Monte-Carlo par chaînes de Markov]], le polynôme de Tutte peut être approximé d'arbitrairement près sur la branche positive de <math>H_2</math>, qui est aussi la fonction de partition du modèle d'Ising ferromagnétique.
Elle exploite le lien étroit entre le modèle d'Ising et le problème du comptage des [[couplage (théorie des graphes)|couplages]] dans un graphe. L'idée derrière ce célèbre résultat de Jerrum et Sinclair<ref>{{harvsp|Jerrum|Sinclair|1993}}.</ref> est de définir une [[chaîne de Markov]] dont les états sont les couplages du graphe donné. Les transitions sont définies en choisissant aléatoirement des arêtes et en modifiant le couplage en conséquence. La chaîne de Markov obtenue est rapidement mélangeante et conduit à des couplages « suffisamment aléatoires » qui peuvent être utilisées pour récupérer la fonction de partition par un échantillonnage aléatoire. L'algorithme obtenu est un [[schéma d'approximation en temps polynomial]] (FPRAS).

== Complexité algorithmique ==
Plusieurs problèmes algorithmiques sont associés aux polynômes de Tutte. Le plus direct est le calcul des coefficients du polynôme de Tutte <math>T_G</math> pour un graphe <math>G</math> donné.

Ceci permet l’évaluation du polynôme de Tutte en tout point ; par exemple l'évaluation de <math>T_G(-2,0)</math> équivaut au calcul du nombre de 3-coloriages de ''G''. Ce problème est [[Sharp-P-complet|#P-complet]], même restreint à la famille des [[graphe planaire|graphes planaires]], de sorte que le calcul des coefficients d'un polynôme de Tutte d'un graphe est [[Sharp-P-complet|#P-difficile]] même pour les [[Graphe complet|graphes complets]].

Un ensemble de problèmes appelés de manière abrégée « Tutte<math>(x,y)</math> » a été étudié ; il s'agit, étant donné un graphe <math>G</math> de calculer, pour un couple de nombres complexes <math>(x,y)</math>, la valeur <math>T_G(x,y)</math>. La difficulté du problème varie avec les coordonnées <math>(x,y)</math>.

=== Calcul exact ===
[[Image:Tractable points of the Tutte polynomial in the real plane.svg|vignette|upright=2|droite|
Le plan de Tutte. À chaque point <math>(x,y)</math> du plan réel est associée la complexité du calcul de <math>T_G(x,y)</math> :<br />
{{Rouge|●}} en un point rouge, le calcul est en temps polynomial ;<br />
{{Bleu|●}} sur une courbe bleue, le problème est #P-difficile en général, mais polynomial pour les graphes planaires ;<br />
● pour tout point des régions blanches, le problème est #P-difficile même pour les graphes planaires bipartis.
]]
Si ''x'' et ''y'' sont tous deux des entiers positifs ou nuls, le problème du calcul de <math>T_G(x,y)</math> est dans la classe [[Sharp-P|#P]]. Pour des [[Entier relatif|entiers relatifs]], le polynôme de Tutte contient des termes négatifs, ce qui place le problème dans la classe de complexité {{Lien|langue=en|fr=GapP}}, qui est la fermeture par [[soustraction]] de la classe [[Sharp-P|#P]]. Pour prendre en compte des coordonnées <math>(x,y)</math> rationnelles, on peut définir une classe correspondant à [[Sharp-P|#P]]<ref name="Goldberg-Jerrum-2008">{{harvsp|Goldberg|Jerrum|2008}}.</ref>.

La complexité algorithmique du calcul exact de <math>T_G(x,y)</math> se partage en deux classes selon la valeur de <math>x, y \in \Complex</math>. Le problème est #P-difficile sauf si <math>(x,y)</math> est un point de l'hyperbole <math>H_1</math> ou est l’un des points de l'ensemble suivant (avec <math>j = e^{2 i\pi/3}</math>) :

:<math>\{ (1,1), (-1,-1), (0,-1), (-1,0), (i,-i), (-i,i), (j,j^2), (j^2,j)\}</math>,

auquel cas le calcul est en temps polynomial<ref>{{harvsp|Jaeger|Vertigan|Welsh|1990}}.</ref>. Pour les graphes planaires, le problème devient polynomial aussi pour les points sur l'hyperbole <math>H_2</math>, mais reste #P-difficile pour les autres points, même pour les graphes planaires bipartis<ref>{{harvsp|Vertigan|Welsh|1992}}.</ref>. Dans la conclusion de son article sur la dichotomie pour les graphes planaires<ref>{{harvsp|Vertigan|2005}}.</ref>, Vertigan note que le même résultat reste valable même pour la restriction supplémentaire aux graphes de degré au plus trois, à l'exception du point <math>T_G(0,-2)</math>, qui compte les flots « nowhere-zero » <math>Z_3</math> pour lequel le polynôme se calcul en temps polynomial.

Ces résultats admettent divers cas particuliers intéressants. Par exemple, le problème du calcul de la fonction de partition du modèle d'Ising est #P-difficile en général, même avec l'algorithme d'Onsager et Fisher de résolution dans les treillis planaires. De même, les polynômes de Jones sont #P-difficiles à évaluer. Enfin, le calcul du nombre de 4-coloriages d'un graphe planaire est #P-complet, alors que le [[problème de décision]] est trivial par le [[théorème des quatre couleurs]]. En revanche, compter le nombre de 3-coloriages d'un graphe planaire est #P-complet parce que le problème de décision est connu pour être NP-complet.

=== Approximation ===

Les points qui possèdent un bon [[algorithme d'approximation]] sont peu connus. En dehors des points pour lequel le calcul exact peut être fait en temps polynomial, le seul algorithme d'approximation connu pour <math>T_G(x,y)</math> est l'algorithme FPRAS de Jerrum et Sinclair, qui est valable pour les points sur l'hyperbole d'Ising <math>H_2</math> pour ''y'' > 0. Si le graphe donné est restreint aux instances denses, avec degré <math>\Omega(n)</math>, alors il existe un FPRAS pour ''x'' ≥ 1, ''y'' ≥ 1<ref>Pour ''x'' ≥ 1 et ''y'' = 1, voir {{harvsp|Annan|1994}}. Pour ''x'' ≥ 1 et ''y'' > 1, voir {{harvsp|Alon|Frieze|Welsh|1995}}.</ref>. Même si les résultats sont moins complets que pour le calcul exact, on sait que de larges portions du plan sont difficiles à approximer<ref name="Goldberg-Jerrum-2008" />.

== Annexes ==

=== Notes ===
{{Traduction/Référence|en|Tutte polynomial|814700906}}
{{Références}}

=== Références ===
;Livres et monographies
{{Début de colonnes|taille=25}}
* {{Ouvrage
 | langue=en
 | prénom1=Norman
 | nom1=Biggs
 | titre=Algebraic Graph Theory
 | lieu=Cambridge
 | éditeur=[[Cambridge University Press]]
 | année=1993
 | numéro d'édition=2
 | pages totales=205
 | isbn=0-521-45897-8
}}.
* {{Ouvrage
 | langue=en
 | prénom1=Béla
 | nom1=Bollobás
 | titre=Modern Graph Theory
 | éditeur=[[Springer Science+Business Media|Springer]]
 | année=1998
 | pages totales=394
 | isbn=978-0-387-98491-9
 | id=Bollobas
}}.
* {{Ouvrage
 |auteur1=Julien Courtiel
 |titre=Combinatoire du polynôme de Tutte et des cartes planaires
 |lieu=Université de Bordeaux I
 |éditeur=Labri
 |nature ouvrage=thèse de doctorat en informatique
 |date=octobre 2014
 |isbn=
 |arxiv=1411.0737
 |lire en ligne=https://arxiv.org/pdf/1411.0737.pdf
}}.
* {{Ouvrage
 | langue=en
 | prénom1=Chris
 | nom1=Godsil
 | lien auteur1=Chris Godsil
 | prénom2=Gordon
 | nom2=Royle
 | lien auteur2=Gordon Royle
 | titre=Algebraic Graph Theory
 | éditeur=[[Springer Science+Business Media|Springer]]
 | année=2004
 | pages totales=439
 | isbn=978-0-387-95220-8
 | lire en ligne=https://books.google.com/books?id=pYfJe-ZVUyAC&printsec=frontcover
}}.
* {{Ouvrage
 | langue=fr
 | prénom1=Pierre
 | nom1=Martin
 | titre=Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck
 | éditeur=[[Université Joseph-Fourier (Grenoble-I)]]
 | nature ouvrage=thèse de doctorat en informatique
 | année=1977
 | isbn=
 | lire en ligne=http://tel.archives-ouvertes.fr/tel-00287330/en
}}.
* {{Ouvrage
 | langue=en
 | prénom1=W. T.
 | nom1=Tutte
 | lien auteur1=William Thomas Tutte
 | titre=Graph Theory
 | éditeur=[[Cambridge University Press]]
 | année=2001
 | pages totales=333
 | isbn=978-0-521-79489-3
 | lire en ligne=https://books.google.com/books?id=uTGhooU37h4C&printsec=frontcover
}}.
* {{Ouvrage
 | langue=en
 | prénom1=Dominic J. A.
 | nom1=Welsh
 | titre=Matroid Theory
 | éditeur=[[Academic Press]]
 | année=1976
 | isbn=0-12-744050-X
}}.
* {{Ouvrage
 | langue=en
 | prénom1=Dominic J. A.
 | nom1=Welsh
 | titre=Complexity
 | sous-titre=Knots, Colourings and Counting
 | éditeur=[[Cambridge University Press]]
 | collection=London Mathematical Society Lecture Note Series
 | année=1993
 | pages totales=163
 | isbn=978-0-521-45740-8
 | lire en ligne=https://books.google.com/books?id=X6xhj81Ro7EC&printsec=frontcover
}}.
* {{Ouvrage
 | langue=en
 | prénom1=Herbert S.
 | nom1=Wilf
 | lien auteur1=Herbert Wilf
 | titre=Algorithms and complexity
 | éditeur=[[Prentice Hall]]
 | année=1986
 | isbn=0-13-021973-8
 | math reviews=897317
 | lire en ligne=https://www.math.upenn.edu/~wilf/AlgoComp.pdf
}}.
{{fin de colonnes}}
;Articles
{{Début de colonnes|taille=25}}
* {{article
 | langue = en
 | nom1 = Alon
 | prénom1 = N.
 | auteur2 = [[Alan Frieze|A. Frieze]]
 | nom3 = Welsh
 | prénom3 = D. J. A.
 | lien auteur3 = Dominic Welsh
 | titre = Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case
 | journal = Random Structures and Algorithms
 | volume = 6
 | numéro = 4
 | pages = 459–478
 | année = 1995
 | doi = 10.1002/rsa.3240060409
}}.
* {{article
 | langue = en
 | nom1 = Annan
 | prénom1 = J. D.
 | titre = A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
 | journal = Combinatorics, Probability and Computing
 | volume = 3
 | numéro = 3
 | pages = 273–283
 | année = 1994
 | doi = 10.1017/S0963548300001188
}}.
* {{article
 | langue = en
 | nom1 = Awan
 | prénom1 = Jordan
 | nom2 = Bernardi
 | prénom2 = Olivier
 | titre = Tutte polynomials for directed graphs
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 140
 | numéro = 
 | pages = 192–247
 | année = 2020
 | arxiv = 1610.01839 
 | doi = 10.1016/j.jctb.2019.05.006
}}.
<!-- B -->
* {{chapitre
 | langue = en
 |id=Bjorklund
 | prénom1 = Andreas
 | nom1 = Björklund
 | prénom2 = Thore
 | nom2 = Husfeldt
 | prénom3 = Petteri
 | nom3 = Kaski
 | prénom4 = Mikko
 | nom4 = Koivisto
 | titre = Computing the Tutte polynomial in vertex-exponential time
 | titre ouvrage= Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)
 | passage = 677–686
 | année = 2008
 | doi = 10.1109/FOCS.2008.40
 | isbn = 978-0-7695-3436-7
}}.
<!-- C -->
* {{article
 | langue = en
 | nom1 = Chung
 | prénom1 = Fan
 | lien auteur1 = Fan Chung
 | nom2 = Yau
 | prénom2 = S.-T.
 | lien auteur2 = Shing-Tung Yau
 | titre = Coverings, heat kernels and spanning trees
 | journal = [[Electronic Journal of Combinatorics]]
 | volume = 6
 | numéro article = R12
 | année = 1999
 | mr = 1667452
 | url = http://www.combinatorics.org/Volume_6/Abstracts/v6i1r12.html
}}.

* {{article
 | langue = en
 | nom1 = Crapo
 | prénom1 = Henry H.
 | titre = The Tutte polynomial
 | journal = [[Aequationes Mathematicae]]
 | volume = 3
 | numéro = 3
 | pages = 211–229
 | année = 1969
 | doi = 10.1007/bf01817442
}}.
<!-- F -->
* {{chapitre
 | langue = en
 | nom = Farr
 | prénom = Graham E.
 | auteurs ouvrage = Geoffrey Grimmett et Colin McDiarmid 
 | titre chapitre = Tutte-Whitney polynomials: some history and generalizations
 | titre ouvrage = Combinatorics, complexity, and chance. A tribute to Dominic Welsh
 | collection = Oxford Lecture Series in Mathematics and its Applications
 | numéro dans collection = 34
 | passage = 28–52
 | année = 2007
 | éditeur = [[Oxford University Press]]
 | isbn = 0-19-857127-5
 | zbl = 1124.05020
}}.
* {{article
 | langue = en
 | nom1 = Fortuin
 | prénom1 = Cees M.
 | nom2 = Kasteleyn
 | prénom2 = Pieter W.
 | titre = On the random-cluster model: I. Introduction and relation to other models
 | journal = [[Physica]]
 | volume = 57
 | numéro = 4
 | pages = 536–564
 | année = 1972
 | éditeur = [[Elsevier (éditeur)|Elsevier]]
 | issn = 0031-8914
 | doi = 10.1016/0031-8914(72)90045-6
}}.

* {{article
 | langue = en
 | nom1 = Goldberg
 | prénom1 = Leslie Ann
 | lien auteur1 = Leslie Ann Goldberg
 | nom2 = Jerrum
 | prénom2 =  Mark
 | lien auteur2 = Mark Jerrum
 | titre = Inapproximability of the Tutte polynomial
 | journal = [[Information and Computation]]
 | volume = 206
 | numéro = 7
 | pages = 908–929
 | année = 2008
 | doi = 10.1016/j.ic.2008.04.003   
}}.
* {{article
 | langue = en
 | nom1 = Haggard
 | prénom1 = Gary
 | nom2 = Pearce
 | prénom2 = David J.
 | nom3 = Royle
 | prénom3 = Gordon
 | titre = Computing Tutte polynomials
 | journal = ACM Transactions on Mathematical Software
 | volume = 37
 | numéro = 3
 | page = Art. 24, 17
 | année = 2010
 | doi = 10.1145/1824801.1824802
 | mr = 2738228
}}.
* {{article
 | langue = en
 | nom1 = Jaeger
 | prénom1 = F.
 | nom2 = Vertigan
 | prénom2 =  D. L.
 | nom3 = Welsh
 | prénom3 = Dominic J. A.
 | lien auteur3 = Dominic Welsh
 | titre = On the computational complexity of the Jones and Tutte polynomials
 | journal = Mathematical Proceedings of the Cambridge Philosophical Society
 | volume = 108
 | pages = 35–53
 | année = 1990
 | doi = 10.1017/S0305004100068936
}}.
* {{article
 | langue = en
 | nom1 = Jerrum
 | prénom1 = Mark
 | lien auteur = Mark Jerrum
 | nom2 = Sinclair
 | prénom2 = Alistair
 | lien auteur2 = Alistair Sinclair
 | titre = Polynomial-time approximation algorithms for the Ising model
 | journal = [[SIAM Journal on Computing]]
 | volume = 22
 | numéro= 5
 | pages = 1087–1116
 | année = 1993
 | doi= 10.1137/0222066
}}.
* {{article
 | langue = en
 | nom1 = Korn
 | prénom1 = Michael
 | nom2 = Pak
 | prénom2 = Igor
 | lien auteur2 = Igor Pak
 | titre = Combinatorial evaluations of the Tutte polynomial
 | journal = preprint
 | année = 2003
 | url = http://www.math.ucla.edu/~pak/papers/tutte7color.pdf
}}.
* {{article
 | langue = en
 | nom1 = Korn
 | prénom1 = Michael
 | nom2 = Pak
 | prénom2 = Igor
 | lien auteur2 = Igor Pak
 | titre = Tilings of rectangles with T-tetrominoes
 | journal = [[Theoretical Computer Science]]
 | volume = 319
 | numéro = 1–3
 | pages = 3–27
 | année = 2004
 | doi = 10.1016/j.tcs.2004.02.023
}}.
* {{article
 |nom1=Lass|prénom1=Bodo
 |titre=Orientations Acycliques et le Polynôme Chromatique
 |journal=European Journal of Combinatorics
 |volume=22|numéro=8|année=2001
 |pages=1101–1123|issn=0195-6698
 |doi=10.1006/eujc.2001.0537
}}.
* {{article
 | langue = en
 | nom = Las Vergnas
 | prénom = Michel
 | lien auteur = Michel Las Vergnas
 | titre = Convexity in oriented matroids
 | journal = [[Journal of Combinatorial Theory]]
 | collection = Series B
 | volume = 29
 | numéro = 2
 | pages = 231–243
 | année = 1980
 | issn = 0095-8956
 | doi = 10.1016/0095-8956(80)90082-9
 | url = http://www.sciencedirect.com/science/article/pii/0095895680900829
 | mr = 586435
}}.
* {{article
 | langue = en
 | nom1 = Las Vergnas
 | prénom1 = Michel
 | lien auteur1 = Michel Las Vergnas
 | titre = On the evaluation at (3, 3) of the Tutte polynomial of a graph
 | journal = [[Journal of Combinatorial Theory]]
 | collection = Series B
 | volume = 45
 | numéro = 3
 | pages = 367–372
 | année = 1988
 | issn = 0095-8956
 | doi = 10.1016/0095-8956(88)90079-2
 | url = http://www.sciencedirect.com/science/article/pii/0095895688900792
}}.

* {{chapitre
 | langue = en
 |auteur =Michael Monagan
 |titre = Computing Tutte Polynomials
 |auteurs ouvrage =   Hiro-Fumi Yamada etNantel Bergeron  
 |titre ouvrage = 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012))
 |année =2012
 |lieu = Nagoya, Japon
 |collection =  Discrete Mathematics and Theoretical Computer Science (DMTCS), DMTCS Proceedings 
 |hal = 01283134
 |passage =839-850
 |url = https://hal.archives-ouvertes.fr/hal-01283134
}}.
* {{article
 | langue = en
 | nom1 = Pearce
 | prénom1 = David J.
 | nom2 = Haggard
 | prénom2 = Gary
 | nom3 = Royle
 | prénom3 = Gordon
 | titre = Edge-selection heuristics for computing Tutte polynomials
 | journal = Chicago Journal of Theoretical Computer Science
 | page = Article 6, 14
 | année = 2010
 | url = http://cjtcs.cs.uchicago.edu/articles/2010/6/cats9-3-1.pdf
 | mr = 2659710
}}.
* {{chapitre
 | langue = en
 | nom1 = Sekine
 | prénom1 = Kyoko
 | nom2 = Imai
 | prénom2 = Hiroshi
 | nom3 = Tani
 | prénom3 = Seiichiro
 | titre chapitre = Computing the Tutte polynomial of a graph of moderate size
 | titre ouvrage = Algorithms and computations (Cairns, 1995)
 | numéro dans collection = 1004
 | passage = 224–233
 | collection = Lecture Notes in Computer Science
 | éditeur = [[Springer Science+Business Media|Springer]]
 | année = 1995
 | doi = 10.1007/BFb0015427
 | mr = 1400247
}}.
* {{chapitre
 | langue = en
 | nom1 = Sokal
 | prénom1 = Alan D.
 | nom2 = Webb
 | prénom2 = Bridget S.
 | titre = The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
 | titre ouvrage  = Surveys in Combinatorics
 | numéro dans collection = 327
 | passage = 173–226
 | année = 2005
 | collection = London Mathematical Society Lecture Note Series
 | éditeur = [[Cambridge University Press]]
 | doi = 10.1017/CBO9780511734885.009
 | arxiv = math/0503607
}}.

* {{article
 | langue = en
 | nom1 = Tutte
 | prénom1 = W. T.
 | lien auteur1 = William Thomas Tutte
 | titre = Graph-polynomials
 | journal = Advances in Applied Mathematics
 | volume = 32
 | numéro = 1–2
 | année = 2004
 | pages = 5–9
 | doi = 10.1016/S0196-8858(03)00041-1
}}.
* {{article
 | langue = en
 | nom1 = Vertigan
 | prénom1 = D. L.
 | nom2 = Welsh
 | prénom2 = D. J. A.
 | lien auteur2 = Dominic Welsh
 | titre = The Computational Complexity of the Tutte Plane: the Bipartite Case
 | journal = Combinatorics, Probability and Computing
 | volume = 1
 | numéro = 2
 | pages = 181–187
 | année = 1992
 | doi = 10.1017/S0963548300000195
 | url = https://dx.doi.org/10.1017/S0963548300000195
}}.
* {{article
 | langue = en
 | nom = Vertigan
 | prénom = Dirk
 | titre = The Computational Complexity of Tutte Invariants for Planar Graphs
 | journal = [[SIAM Journal on Computing]]
 | volume = 35
 | numéro = 3
 | pages = 690–712
 | année = 2005
 | doi = 10.1137/S0097539704446797
 | url = https://dx.doi.org/10.1137/S0097539704446797
}}.
<!-- W -->

* {{article
 | langue = en
 | nom = Welsh
 | prénom = Dominic J. A.
 | titre = The Tutte polynomial
 | journal = Random Structures & Algorithms
 | volume = 15
 | numéro = 3–4
 | pages = 210–228
 | année = 1999
 | éditeur = [[John Wiley & Sons|Wiley]]
 | issn = 1042-9832
 | doi = 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R
 | url = https://dx.doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4%3C210::AID-RSA2%3E3.0.CO;2-R
}}.
* {{article
 | langue = en
 | nom1 = Welsh
 | prénom1 = Dominic J. A.
 | nom2 = Merino
 | prénom2 = C.
 | titre = The Potts model and the Tutte polynomial
 | journal = [[Journal of Mathematical Physics]]
 | volume = 41
 | numéro = 3
 | année = 2000 
 | doi = 10.1063/1.533181
}}.
{{Fin de colonnes}}

=== Articles liés ===
* {{Lien|langue=en|trad=Bollobás–Riordan polynomial|fr=polynôme de Bollobás–Riordan}}
=== Liens externes ===
* <!-- Modèle:EncycloMath -->{{EncycloMath|titre=Tutte polynomial|id=p/t120210}}
* <!-- Modèle:MathWorld -->{{MathWorld | nom_url=TuttePolynomial| titre=Tutte polynomial}}
* {{Planetmath|titre=Chromatic polynomial}}.

{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Mathématiques discrètes]]
[[Catégorie:Théorie des graphes]]
[[Catégorie:Combinatoire]]
[[Catégorie:Polynôme]]
[[Catégorie:Invariant de graphe]]