Polynôme de Tutte

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é ${\displaystyle G}$ 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 ${\displaystyle G}$. É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 modèle de Potts (en) 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^[1]

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^[2],[3],[4].

Le polynôme ${\displaystyle x^{4}+x^{3}+x^{2}y}$ est le polynôme de Tutte du graphe taureau. La ligne rouge indique l'intersection avec le plan ${\displaystyle y=0}$, équivalent au polynôme chromatique.

Définitions et exemples

Définitions équivalentes

Soit ${\displaystyle G=(V,E)}$ un graphe non orienté, avec ensemble de sommets ${\displaystyle V}$ et ensemble d'arêtes ${\displaystyle E}$. Pour ${\displaystyle A\subseteq E}$, on note ${\displaystyle (V,A)}$ le graphe partiel qui a les mêmes sommets que ${\displaystyle G}$, et ses arêtes dans ${\displaystyle A}$.

Definition.- Le polynôme de Tutte d'un graphe ${\displaystyle G=(V,E)}$ est le polynôme ${\displaystyle T_{G}(x,y)}$ défini par :

${\displaystyle T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}}$,

où ${\displaystyle k(A)}$ est le nombre de composantes connexes du graphe ${\displaystyle (V,A)}$. L'exposant ${\displaystyle k(A)+|A|-|V|}$ du deuxième facteur est le nombre cyclomatique de ${\displaystyle (V,A)}$.

On peut donner une formulation légèrement différente de la même définition en posant

${\displaystyle r(A)=|V|-k(A)}$,

où ${\displaystyle r(A)}$ est le rang de Whitney du graphe ${\displaystyle (V,A)}$. La fonction génératrice des rangs de Whitney est définie par :

${\displaystyle R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}}$.

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

${\displaystyle T_{G}(x,y)=R_{G}(x-1,y-1)}$.

Le polynôme dichromatique ${\displaystyle Q_{G}}$ de Tutte résulte d'une autre transformation simple. On a :

${\displaystyle T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1)}$.

Définition originale.- La définition originale de ${\displaystyle T_{G}}$ de Tutte est équivalente, mais moins facile à formuler. Pour un graphe connexe ${\displaystyle G}$, on a

${\displaystyle T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},}$

où ${\displaystyle t_{ij}}$ est le nombre d'arbres couvrants d'« activité interne » ${\displaystyle i}$ et d' « activité interne » ${\displaystyle j}$^[5].

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

${\displaystyle 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}}}$

selon que ${\displaystyle e}$ est boucle un isthme, ou ni l'un ni l'autre, avec la condition initiale

${\displaystyle T_{G}=1}$ si ${\displaystyle G}$ ne contient pas d'arête.

Le « random cluster model » de la mécanique statistique dû à Fortuin et Kasteleyn 1972 fournit encore une autre définition équivalente^[6] : Le polynôme

${\displaystyle Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}}$

est lié à ${\displaystyle T_{G}}$ par la transformation ^[7] :

${\displaystyle T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.}$

Propriétés

Le polynôme de Tutte se factorise pour les composantes connexes : Si ${\displaystyle G}$ est l'union disjointe de graphes ${\displaystyle H}$ et ${\displaystyle H'}$, alors

${\displaystyle T_{G}=T_{H}\cdot T_{H'}}$.

Si ${\displaystyle G}$ est un graphe planaire et si ${\displaystyle G^{*}}$ dénote son graphe dual, alors

${\displaystyle T_{G}(x,y)=T_{G^{*}}(y,x)}$.

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 ${\displaystyle m}$ arêtes est ${\displaystyle x^{m}}$.

Un polynôme de Tutte peut être donné sous forme de table, en présentant dans un tableau le coefficient ${\displaystyle t_{ij}}$ de ${\displaystyle x^{i}y^{j}}$ en ligne ${\displaystyle i}$ et colonne ${\displaystyle j}$. Par exemple, le polynôme de Tutte du graphe de Petersen, qui est :

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

est donné par la table suivante :

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 :

${\displaystyle {\begin{aligned}&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{aligned}}}$

Note historique

L'intérêt de W. T. Tutte pour la formule de contraction-suppression remonte à ses études undergraduate au Trinity College de Cambridge, motivé par les rectangles parfaits (en) 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 »^[8]. 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 »^[8] 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 »^[9] 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^[10].

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^[11] sur les random cluster model (en), 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^[10].

Spécialisations

En faisant varier les valeurs de ${\displaystyle (x,y)}$, 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

Le polynôme chromatique dans le plan de Tutte.

Pour ${\displaystyle y=0}$, le polynôme de Tutte se spécialises en le polynôme chromatique :

${\displaystyle \chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),}$

où ${\displaystyle k(G)}$ est le nombre de composantes connexes de ${\displaystyle G}$.

Pour des valeurs entières de ${\displaystyle \lambda }$, la valeur du polynôme chromatique ${\displaystyle \chi _{G}(\lambda )}$ est égale au nombre de colorations du graphe ${\displaystyle G}$ en utilisant ${\displaystyle \lambda }$ couleurs. Clairement ${\displaystyle \chi _{G}(\lambda )}$ ne dépend pas de l’ensemble de couleurs. Ce qui est moins clair, c'est que c'est la valeur en ${\displaystyle \lambda }$ d'un polynôme à coefficients entiers. Pour voir cela, on observe que :

1. si G a n sommets et pas d'arêtes, alors ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n}}$.
2. si G contient une boucle, alors ${\displaystyle \chi _{G}(\lambda )=0}$.
3. si e est une arête qui n'est pas une boucle, alors

${\displaystyle \chi _{G}(\lambda )=\chi _{G\setminus e}(\lambda )-\chi _{G/e}(\lambda ).}$

Ces trois conditions permettent de calculer ${\displaystyle \chi _{G}(\lambda )}$ 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 ${\displaystyle \chi _{G}(\lambda )}$ compte des propriétés combinatoires, indépendamment de la récurrence. En particulier,

${\displaystyle T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)}$

donne le nombre d'orientations acycliques du graphe.

Polynôme de Jones

Polynômes de Jones dans le plan de Tutte.

Sur l'hyperbole ${\displaystyle xy=1}$, 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)

${\displaystyle T_{G}(2,1)}$ compte le nombre de forêts, c'est-à-dire le nombre des sous-ensembles d'arêtes sans cycle.

(1,1)

${\displaystyle T_{G}(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, ${\displaystyle T_{G}(1,1)}$ compte le nombre d'arbres couvrants.

(1,2)

${\displaystyle T_{G}(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 )

${\displaystyle T_{G}(2,0)}$ compte le nombre d'orientations acycliques (en) de G^[12],[13].

(0,2)

${\displaystyle T_{G}(0,2)}$ compte le nombre d'orientations fortement connexes de G^[14].

(0,−2)

Si G est un graphe 4-régulier, alors

${\displaystyle (-1)^{|V|+k(G)}T_{G}(0,-2)}$

compte le nombre d'orientations eulériennes de G. Ici, ${\displaystyle k(G)}$ est le nombre de composantes connexes de G^[12].

(3,3)

Si G est un graphe grille de paramètres ${\displaystyle m\times n}$, alors ${\displaystyle 2T_{G}(3,3)}$ compte le nombre de manière de paver un rectangle de largeur 4m et de hauteur 4n avec des tétrominos^[15],[16].

Si G est un graphe planaire, alors ${\displaystyle 2T_{G}(3,3)}$ 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 »)^[17].

Modèles de Potts et d'Ising

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 ${\displaystyle H_{2}}$ définie par :

${\displaystyle H_{2}:\quad (x-1)(y-1)=2}$.

Sur cette hyperbole, le polynôme de Tutte se spécialise en la fonction de partition ${\displaystyle Z(\cdot ),}$ du modèle d'Ising étudiée en physique statistique. Plus précisément, le long de l'hyperbole ${\displaystyle H_{2}}$ ces deux fonctions sont liées par l'équation^[18] :

${\displaystyle 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).}$

Le lien avec l'hyperbole vient de ce que

${\displaystyle (\coth \alpha -1)\left(e^{2\alpha }-1\right)=2}$

pour tout nombre complexe ${\displaystyle \alpha }$.

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

${\displaystyle H_{q}:\quad (x-1)(y-1)=q}$,

le polynôme de Tutte se spécialise en la fonction de partition du modèle de Potts (en) à q états. Diverses quantités physiques analysées dans le contexte du modèle de Potts se transposent en des parties spécifiques de ${\displaystyle H_{q}}$.

Correspondances entre le modèle de Potts et le plan de Tutte^[19]

modèle de Potts	polynôme de Tutte
Ferromagnétisme	Branche positive de ${\displaystyle H_{q}}$
Antiferromagnétisme	Branche négative de ${\displaystyle H_{q}}$ avec ${\displaystyle y>0}$
Haute température	Asymptote de ${\displaystyle H_{q}}$ pour ${\displaystyle y=1}$
Basse temperature ferromagnétique	Branche positive de ${\displaystyle H_{q}}$ asymptotique en ${\displaystyle x=1}$
Température nulle antiferromagnetique	q-coloration du graphe, c'est-à-dire ${\displaystyle x=1-q,y=0}$.

Polynôme de flot

Le polynôme de flot dans le plan de Tutte.

Au point ${\displaystyle x=0}$, 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 (« nowhere-zero flow ») est une affectations de valeurs de « flot » ${\displaystyle 1,2,\dots ,k-1}$ 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 ${\displaystyle C_{G}(k)}$ 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 ${\displaystyle G^{*}}$ par le théorème de Tutte suivant :

${\displaystyle C_{G}(k)=k^{-1}\chi _{G^{*}}(k)}$.

La connexion avec le polynôme de Tutte est donnée par :

${\displaystyle C_{G}(k)=(-1)^{|E|+|V|+k(G)}T_{G}(0,1-k)}$.

Polynôme de fiabilité

Le polynôme de fiabilité dans le plan de Tutte.

Pour ${\displaystyle x=1}$, 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 ${\displaystyle R_{G}(p)}$ 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 :

${\displaystyle R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}(1,1/p)}$.

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 ${\displaystyle G=(V,E)}$, c'est le polynôme

${\displaystyle Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},}$

où ${\displaystyle k(A)}$ est le nombre de composantes connexes du graphe partiel ${\displaystyle (V,A)}$. Ce polynôme est relié au « corank-nullity polynomial » par

${\displaystyle Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).}$

Le polynôme dichromatique ne se généralise pas aux matroïdes parce ${\displaystyle k(A)}$ 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 ${\displaystyle m_{\vec {G}}(x)}$ d'un graphe orienté 4-régulier ${\displaystyle {\vec {G}}}$ a été défini par Pierre Martin in 1977^[20]. Il a prouvé que si ${\displaystyle G}$ est un graphe planaire et si ${\displaystyle {\vec {G}}_{m}}$ est son graphe médial orienté, alors

${\displaystyle T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).}$

Algorithmes

Suppression–contraction

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, ${\displaystyle x^{3}+2x^{2}+y^{2}+2xy+x+y}$. Basé sur (Welsh et Merino 2000).

La formule de récurrence de suppression–contraction pour le polynôme de Tutte s'écrit :

${\displaystyle T_{G}(x,y)=T_{G-e}(x,y)+T_{G/e}(x,y)}$,

lorsque ${\displaystyle e}$ 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,

${\displaystyle t(n+m)=t(n+m-1)+t(n+m-2)}$ ;

cette relation est similaire à celle des nombres de Fibonacci avec pour solution^[21] :

${\displaystyle t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m}).}$

L'analyse peut être améliorée par un facteur polynomial en le nombre ${\displaystyle \tau (G)}$ d'arbre couvrants du graphe donné^[22]. Pour des graphes creux, avec ${\displaystyle m=O(n)}$ ce temps de calcul est en ${\displaystyle O(\exp(n))}$. Pour les graphes réguliers de degré k, le nombre d'arbres couvrants peut être borné par

${\displaystyle \tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),}$ avec ${\displaystyle \nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{k/2-1}}}}$,

de sorte que l'algorithme de suppression–contraction s'exécute avec un facteur polynomial de cette borne. On a par exemple^[23] : ${\displaystyle \nu _{5}\approx 4.4066.}$

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^{[22],[24],[25]}. Le choix de l'arête à supprimer s'avère primordial^[26].

É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 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 .

${\displaystyle T_{G}(1,1)}$ est égal au nombre ${\displaystyle \tau (G)}$ d'arbres couvrants d'un graphe connexe. Cette valeur peut se calculer en temps polynomial en tant que 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 ${\displaystyle T_{G}(-1,-1)}$ 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 ${\displaystyle H_{2}}$, 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 Fisher, Kasteleyn et Temperley pour calculer le nombre de pavages par des 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 ${\displaystyle H_{2}}$, 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 couplages dans un graphe. L'idée derrière ce célèbre résultat de Jerrum et Sinclair^[27] 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 ${\displaystyle T_{G}}$ pour un graphe ${\displaystyle G}$ donné.

Ceci permet l’évaluation du polynôme de Tutte en tout point ; par exemple l'évaluation de ${\displaystyle T_{G}(-2,0)}$ équivaut au calcul du nombre de 3-coloriages de G. Ce problème est #P-complet, même restreint à la famille des graphes planaires, de sorte que le calcul des coefficients d'un polynôme de Tutte d'un graphe est #P-difficile même pour les graphes complets.

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

Calcul exact

Le plan de Tutte. À chaque point ${\displaystyle (x,y)}$ du plan réel est associée la complexité du calcul de ${\displaystyle T_{G}(x,y)}$ :
● en un point rouge, le calcul est en temps polynomial ;
● sur une courbe bleue, le problème est #P-difficile en général, mais polynomial pour les graphes planaires ;
● 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 ${\displaystyle T_{G}(x,y)}$ est dans la classe #P. Pour des entiers relatifs, le polynôme de Tutte contient des termes négatifs, ce qui place le problème dans la classe de complexité GapP (en), qui est la fermeture par soustraction de la classe #P. Pour prendre en compte des coordonnées ${\displaystyle (x,y)}$ rationnelles, on peut définir une classe correspondant à #P^[28].

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

${\displaystyle \{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),(j,j^{2}),(j^{2},j)\}}$,

auquel cas le calcul est en temps polynomial^[29]. Pour les graphes planaires, le problème devient polynomial aussi pour les points sur l'hyperbole ${\displaystyle H_{2}}$, mais reste #P-difficile pour les autres points, même pour les graphes planaires bipartis^[30]. Dans la conclusion de son article sur la dichotomie pour les graphes planaires^[31], 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 ${\displaystyle T_{G}(0,-2)}$, qui compte les flots « nowhere-zero » ${\displaystyle Z_{3}}$ 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 ${\displaystyle T_{G}(x,y)}$ est l'algorithme FPRAS de Jerrum et Sinclair, qui est valable pour les points sur l'hyperbole d'Ising ${\displaystyle H_{2}}$ pour y > 0. Si le graphe donné est restreint aux instances denses, avec degré ${\displaystyle \Omega (n)}$, alors il existe un FPRAS pour x ≥ 1, y ≥ 1^[32]. 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^[28].

Annexes

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tutte polynomial » (voir la liste des auteurs).

1. Courtiel 2014 présente une synthèse.
2. Bollobás 1998, chapter 10.
3. Biggs 1993, chapter 13.
4. Godsil et Royle 2004, chap. 15.
5. 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.
6. Sokal 2005.
7. Sokal 2005, eq. (2.26).
8. Tutte 2004.
9. Expression de Welsh.
10. Farr 2007.
11. Fortuin et Kasteleyn 1972.
12. Welsh 1999.
13. Lass 2001.
14. Las Vergnas 1980.
15. Korn et Pak 2004.
16. Korn et Pak 2003 donnent des interprétations combintoires du polynôme de Tutte en de nombreux autres points.
17. Las Vergnas 1988.
18. Welsh 1993, p. 62.
19. Welsh et Merino 2000.
20. Martin 1977.
21. Wilf 1986, p. 46.
22. Sekine, Imai et Tani 1995.
23. Chung et Yau 1999, d'après Björklund et al. 2008.
24. Haggard, Pearce et Royle 2010.
25. Pearce, Haggard et Royle 2010.
26. Monagan 2012.
27. Jerrum et Sinclair 1993.
28. Goldberg et Jerrum 2008.
29. Jaeger, Vertigan et Welsh 1990.
30. Vertigan et Welsh 1992.
31. Vertigan 2005.
32. Pour x ≥ 1 et y = 1, voir Annan 1994. Pour x ≥ 1 et y > 1, voir Alon, Frieze et Welsh 1995.

Références

Livres et monographies

• (en) Norman Biggs, Algebraic Graph Theory, Cambridge, Cambridge University Press, 1993, 2^e éd., 205 p. (ISBN 0-521-45897-8).
• (en) Béla Bollobás, Modern Graph Theory, Springer, 1998, 394 p. (ISBN 978-0-387-98491-9).
• Julien Courtiel, Combinatoire du polynôme de Tutte et des cartes planaires (thèse de doctorat en informatique), Université de Bordeaux I, Labri, octobre 2014 (arXiv 1411.0737, lire en ligne).
• (en) Chris Godsil et Gordon Royle, Algebraic Graph Theory, Springer, 2004, 439 p. (ISBN 978-0-387-95220-8, lire en ligne).
• Pierre Martin, Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (thèse de doctorat en informatique), Université Joseph-Fourier (Grenoble-I), 1977 (lire en ligne).
• (en) W. T. Tutte, Graph Theory, Cambridge University Press, 2001, 333 p. (ISBN 978-0-521-79489-3, lire en ligne).
• (en) Dominic J. A. Welsh, Matroid Theory, Academic Press, 1976 (ISBN 0-12-744050-X).
• (en) Dominic J. A. Welsh, Complexity : Knots, Colourings and Counting, Cambridge University Press, coll. « London Mathematical Society Lecture Note Series », 1993, 163 p. (ISBN 978-0-521-45740-8, lire en ligne).
• (en) Herbert S. Wilf, Algorithms and complexity, Prentice Hall, 1986 (ISBN 0-13-021973-8, MR 897317, lire en ligne).

Articles

• (en) N. Alon, A. Frieze et D. J. A. Welsh, « Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case », Random Structures and Algorithms, vol. 6, n^o 4,‎ 1995, p. 459–478 (DOI 10.1002/rsa.3240060409).
• (en) J. D. Annan, « A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs », Combinatorics, Probability and Computing, vol. 3, n^o 3,‎ 1994, p. 273–283 (DOI 10.1017/S0963548300001188).
• (en) Jordan Awan et Olivier Bernardi, « Tutte polynomials for directed graphs », Journal of Combinatorial Theory, Series B, vol. 140,‎ 2020, p. 192–247 (DOI 10.1016/j.jctb.2019.05.006, arXiv 1610.01839).
• (en) Andreas Björklund, Thore Husfeldt, Petteri Kaski et Mikko Koivisto, « Computing the Tutte polynomial in vertex-exponential time », dans Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), 2008 (ISBN 978-0-7695-3436-7, DOI 10.1109/FOCS.2008.40), p. 677–686.
• (en) Fan Chung et S.-T. Yau, « Coverings, heat kernels and spanning trees », Electronic Journal of Combinatorics, vol. 6,‎ 1999, article n^o R12 (MR 1667452, lire en ligne).

• (en) Henry H. Crapo, « The Tutte polynomial », Aequationes Mathematicae, vol. 3, n^o 3,‎ 1969, p. 211–229 (DOI 10.1007/bf01817442).
• (en) Graham E. Farr, « Tutte-Whitney polynomials: some history and generalizations », dans Geoffrey Grimmett et Colin McDiarmid, Combinatorics, complexity, and chance. A tribute to Dominic Welsh, Oxford University Press, coll. « Oxford Lecture Series in Mathematics and its Applications » (n^o 34), 2007 (ISBN 0-19-857127-5, zbMATH 1124.05020), p. 28–52.
• (en) Cees M. Fortuin et Pieter W. Kasteleyn, « On the random-cluster model: I. Introduction and relation to other models », Physica, Elsevier, vol. 57, n^o 4,‎ 1972, p. 536–564 (ISSN 0031-8914, DOI 10.1016/0031-8914(72)90045-6).

• (en) Leslie Ann Goldberg et Mark Jerrum, « Inapproximability of the Tutte polynomial », Information and Computation, vol. 206, n^o 7,‎ 2008, p. 908–929 (DOI 10.1016/j.ic.2008.04.003).
• (en) Gary Haggard, David J. Pearce et Gordon Royle, « Computing Tutte polynomials », ACM Transactions on Mathematical Software, vol. 37, n^o 3,‎ 2010, Art. 24, 17 (DOI 10.1145/1824801.1824802, MR 2738228).
• (en) F. Jaeger, D. L. Vertigan et Dominic J. A. Welsh, « On the computational complexity of the Jones and Tutte polynomials », Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108,‎ 1990, p. 35–53 (DOI 10.1017/S0305004100068936).
• (en) Mark Jerrum et Alistair Sinclair, « Polynomial-time approximation algorithms for the Ising model », SIAM Journal on Computing, vol. 22, n^o 5,‎ 1993, p. 1087–1116 (DOI 10.1137/0222066).
• (en) Michael Korn et Igor Pak, « Combinatorial evaluations of the Tutte polynomial », preprint,‎ 2003 (lire en ligne).
• (en) Michael Korn et Igor Pak, « Tilings of rectangles with T-tetrominoes », Theoretical Computer Science, vol. 319, n^os 1–3,‎ 2004, p. 3–27 (DOI 10.1016/j.tcs.2004.02.023).
• Bodo Lass, « Orientations Acycliques et le Polynôme Chromatique », European Journal of Combinatorics, vol. 22, n^o 8,‎ 2001, p. 1101–1123 (ISSN 0195-6698, DOI 10.1006/eujc.2001.0537).
• (en) Michel Las Vergnas, « Convexity in oriented matroids », Journal of Combinatorial Theory, vol. 29, n^o 2,‎ 1980, p. 231–243 (ISSN 0095-8956, DOI 10.1016/0095-8956(80)90082-9, MR 586435, lire en ligne).
• (en) Michel Las Vergnas, « On the evaluation at (3, 3) of the Tutte polynomial of a graph », Journal of Combinatorial Theory, vol. 45, n^o 3,‎ 1988, p. 367–372 (ISSN 0095-8956, DOI 10.1016/0095-8956(88)90079-2, lire en ligne).

• (en) Michael Monagan, « Computing Tutte Polynomials », dans Hiro-Fumi Yamada etNantel Bergeron, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)), Nagoya, Japon, coll. « Discrete Mathematics and Theoretical Computer Science (DMTCS), DMTCS Proceedings », 2012 (HAL hal-01283134, lire en ligne), p. 839-850.
• (en) David J. Pearce, Gary Haggard et Gordon Royle, « Edge-selection heuristics for computing Tutte polynomials », Chicago Journal of Theoretical Computer Science,‎ 2010, Article 6, 14 (MR 2659710, lire en ligne).
• (en) Kyoko Sekine, Hiroshi Imai et Seiichiro Tani, « Computing the Tutte polynomial of a graph of moderate size », dans Algorithms and computations (Cairns, 1995), Springer, coll. « Lecture Notes in Computer Science » (n^o 1004), 1995 (DOI 10.1007/BFb0015427, MR 1400247), p. 224–233.
• (en) Alan D. Sokal et Bridget S. Webb, « The multivariate Tutte polynomial (alias Potts model) for graphs and matroids », dans Surveys in Combinatorics, Cambridge University Press, coll. « London Mathematical Society Lecture Note Series » (n^o 327), 2005 (DOI 10.1017/CBO9780511734885.009, arXiv math/0503607), p. 173–226.

• (en) W. T. Tutte, « Graph-polynomials », Advances in Applied Mathematics, vol. 32, n^os 1–2,‎ 2004, p. 5–9 (DOI 10.1016/S0196-8858(03)00041-1).
• (en) D. L. Vertigan et D. J. A. Welsh, « The Computational Complexity of the Tutte Plane: the Bipartite Case », Combinatorics, Probability and Computing, vol. 1, n^o 2,‎ 1992, p. 181–187 (DOI 10.1017/S0963548300000195, lire en ligne).
• (en) Dirk Vertigan, « The Computational Complexity of Tutte Invariants for Planar Graphs », SIAM Journal on Computing, vol. 35, n^o 3,‎ 2005, p. 690–712 (DOI 10.1137/S0097539704446797, lire en ligne).

• (en) Dominic J. A. Welsh, « The Tutte polynomial », Random Structures & Algorithms, Wiley, vol. 15, n^os 3–4,‎ 1999, p. 210–228 (ISSN 1042-9832, DOI 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R, lire en ligne).
• (en) Dominic J. A. Welsh et C. Merino, « The Potts model and the Tutte polynomial », Journal of Mathematical Physics, vol. 41, n^o 3,‎ 2000 (DOI 10.1063/1.533181).

Articles liés

• polynôme de Bollobás–Riordan (en)

Liens externes

• (en) « Tutte polynomial », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
• (en) Eric W. Weisstein, « Tutte polynomial », sur MathWorld
• (en) « Chromatic polynomial », sur PlanetMath.