Polynôme_de_Tutte (original) (raw)

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

Property	Value
dbo:abstract	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) 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 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. (fr)
dbo:namedAfter	dbpedia-fr:William_Tutte
dbo:thumbnail	wiki-commons:Special:FilePath/Tutte_polynomial_and_...omial_of_the_Bull_graph.jpg?width=300
dbo:wikiPageExternalLink	http://tel.archives-ouvertes.fr/tel-00287330/en http://www.sciencedirect.com/science/article/pii/0095895680900829 http://www.sciencedirect.com/science/article/pii/0095895688900792 https://arxiv.org/pdf/1411.0737.pdf https://books.google.com/books%3Fid=X6xhj81Ro7EC&printsec=frontcover https://books.google.com/books%3Fid=pYfJe-ZVUyAC&printsec=frontcover https://books.google.com/books%3Fid=uTGhooU37h4C&printsec=frontcover http://www.math.ucla.edu/~pak/papers/tutte7color.pdf http://cjtcs.cs.uchicago.edu/articles/2010/6/cats9-3-1.pdf https://dx.doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4%3C210::AID-RSA2%3E3.0.CO;2-R https://dx.doi.org/10.1017/S0963548300000195 https://dx.doi.org/10.1137/S0097539704446797 https://hal.archives-ouvertes.fr/hal-01283134 http://planetmath.org/chromaticpolynomialChromatic http://www.combinatorics.org/Volume_6/Abstracts/v6i1r12.html https://www.math.upenn.edu/~wilf/AlgoComp.pdf
dbo:wikiPageID	11374298 (xsd:integer)
dbo:wikiPageLength	43999 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID	188761975 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Polynôme category-fr:Invariant_de_graphe dbpedia-fr:Academic_Press dbpedia-fr:Aequationes_Mathematicae dbpedia-fr:Alan_Frieze dbpedia-fr:Algorithme_FKT dbpedia-fr:Antiferromagnétisme dbpedia-fr:Arbre_(théorie_des_graphes) dbpedia-fr:Arbre_couvrant dbpedia-fr:Boucle_(théorie_des_graphes) dbpedia-fr:Cambridge_University_Press category-fr:Combinatoire category-fr:Mathématiques_discrètes category-fr:Théorie_des_graphes dbpedia-fr:Chaîne_de_Markov dbpedia-fr:Coloration_de_graphe dbpedia-fr:Combinatoire dbpedia-fr:Contraction_d'arête dbpedia-fr:Couplage_(théorie_des_graphes) dbpedia-fr:Dominos_(jeu) dbpedia-fr:Déterminant_(mathématiques) dbpedia-fr:Electronic_Journal_of_Combinatorics dbpedia-fr:Elsevier dbpedia-fr:Ferromagnétisme dbpedia-fr:Fonction_de_partition dbpedia-fr:Graphe_connexe dbpedia-fr:Graphe_de_Petersen dbpedia-fr:Graphe_dual dbpedia-fr:Graphe_eulérien dbpedia-fr:Graphe_grille dbpedia-fr:Graphe_médial dbpedia-fr:Graphe_non_orienté dbpedia-fr:Graphe_octaédrique dbpedia-fr:Graphe_planaire dbpedia-fr:Hassler_Whitney dbpedia-fr:Information_and_Computation dbpedia-fr:Informatique_théorique dbpedia-fr:Isomorphisme_de_graphes dbpedia-fr:Isthme_(théorie_des_graphes) dbpedia-fr:John_Wiley_&_Sons dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Journal_of_Mathematical_Physics dbpedia-fr:Lexique_de_la_théorie_des_graphes dbpedia-fr:Modèle_d'Ising dbpedia-fr:Méthode_de_Monte-Carlo_par_chaînes_de_Markov dbpedia-fr:Oxford_University_Press dbpedia-fr:Pavage_du_plan dbpedia-fr:Pfaffien dbpedia-fr:Physica dbpedia-fr:Physique_statistique dbpedia-fr:PlanetMath dbpedia-fr:Polynôme dbpedia-fr:Polynôme_chromatique dbpedia-fr:Polynôme_de_Jones dbpedia-fr:Prentice_Hall dbpedia-fr:Problème_algorithmique dbpedia-fr:Ronald_M._Foster dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:Schéma_d'approximation_en_temps_polynomial dbpedia-fr:Sharp-P dbpedia-fr:Sharp-P-complet dbpedia-fr:Sous-graphe dbpedia-fr:Springer_Science+Business_Media dbpedia-fr:Suite_de_Fibonacci dbpedia-fr:Série_génératrice dbpedia-fr:Theoretical_Computer_Science dbpedia-fr:Théorie_algébrique_des_graphes dbpedia-fr:Théorie_des_codes dbpedia-fr:Théorie_des_graphes dbpedia-fr:Théorie_des_nœuds dbpedia-fr:Théorie_des_réseaux dbpedia-fr:Théorème_de_Kirchhoff dbpedia-fr:Théorème_de_Robbins dbpedia-fr:Théorème_des_quatre_couleurs dbpedia-fr:Trinity_College_(Cambridge) dbpedia-fr:Tétromino dbpedia-fr:Université_Joseph-Fourier dbpedia-fr:William_Tutte dbpedia-fr:Élimination_de_Gauss-Jordan dbpedia-fr:Matrice_laplacienne dbpedia-fr:Matroïde dbpedia-fr:Michael_Fisher dbpedia-fr:Fichier:Chromatic_in_the_Tutte_plane.jpg dbpedia-fr:Fichier:Deletion-contraction.svg dbpedia-fr:Fichier:Flow_in_the_Tutte_plane.jpg dbpedia-fr:Fichier:Jones_in_the_Tutte_plane.jpg dbpedia-fr:Fichier:Potts_and_Ising_in_the_Tutte_plane.jpg dbpedia-fr:Fichier:Reliability_in_the_Tutte_plane.jpg dbpedia-fr:Fichier:Tractable_points_of_the_Tutte_polynomial_in_the_real_plane.svg dbpedia-fr:Fichier:Tutte_polynomial_and_chromatic_polynomial_of_the_Bull_graph.jpg
prop-fr:année	1969 (xsd:integer) 1972 (xsd:integer) 1976 (xsd:integer) 1977 (xsd:integer) 1980 (xsd:integer) 1986 (xsd:integer) 1988 (xsd:integer) 1990 (xsd:integer) 1992 (xsd:integer) 1993 (xsd:integer) 1994 (xsd:integer) 1995 (xsd:integer) 1998 (xsd:integer) 1999 (xsd:integer) 2000 (xsd:integer) 2001 (xsd:integer) 2003 (xsd:integer) 2004 (xsd:integer) 2005 (xsd:integer) 2007 (xsd:integer) 2008 (xsd:integer) 2010 (xsd:integer) 2012 (xsd:integer) 2020 (xsd:integer)
prop-fr:arxiv	1411.073700 (xsd:double) 1610.018390 (xsd:double) math/0503607 (fr)
prop-fr:auteur	dbpedia-fr:Alan_Frieze Julien Courtiel (fr) Michael Monagan (fr)
prop-fr:auteursOuvrage	Geoffrey Grimmett et Colin McDiarmid (fr) Hiro-Fumi Yamada etNantel Bergeron (fr)
prop-fr:collection	London Mathematical Society Lecture Note Series (fr) Lecture Notes in Computer Science (fr) Series B (fr) Oxford Lecture Series in Mathematics and its Applications (fr) Discrete Mathematics and Theoretical Computer Science , DMTCS Proceedings (fr)
prop-fr:date	octobre 2014 (fr)
prop-fr:doi	10.100200 (xsd:double) 10.100600 (xsd:double) 10.100700 (xsd:double) 10.101600 (xsd:double) 10.101700 (xsd:double) 10.106300 (xsd:double) 10.110900 (xsd:double) 10.113700 (xsd:double) 10.114500 (xsd:double)
prop-fr:fr	modèle de Potts (fr) GapP (fr) orientation acyclique (fr) polynôme de Bollobás–Riordan (fr) random cluster model (fr) rectangle parfait (fr)
prop-fr:hal	1283134 (xsd:integer)
prop-fr:id	Bjorklund (fr) Bollobas (fr) p/t120210 (fr)
prop-fr:isbn	0 (xsd:integer) 978 (xsd:integer)
prop-fr:issn	31 (xsd:integer) 95 (xsd:integer) 195 (xsd:integer) 1042 (xsd:integer)
prop-fr:journal	dbpedia-fr:Aequationes_Mathematicae dbpedia-fr:Electronic_Journal_of_Combinatorics dbpedia-fr:Information_and_Computation dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Journal_of_Mathematical_Physics dbpedia-fr:Physica dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:Theoretical_Computer_Science Advances in Applied Mathematics (fr) Mathematical Proceedings of the Cambridge Philosophical Society (fr) European Journal of Combinatorics (fr) Combinatorics, Probability and Computing (fr) Random Structures & Algorithms (fr) ACM Transactions on Mathematical Software (fr) Journal of Combinatorial Theory, Series B (fr) Random Structures and Algorithms (fr) preprint (fr) Chicago Journal of Theoretical Computer Science (fr)
prop-fr:langue	en (fr) fr (fr)
prop-fr:lienAuteur	Herbert Wilf (fr) Dominic Welsh (fr) Fan Chung (fr) Chris Godsil (fr) Gordon Royle (fr) Igor Pak (fr) Alistair Sinclair (fr) Leslie Ann Goldberg (fr) Mark Jerrum (fr) Michel Las Vergnas (fr) Shing-Tung Yau (fr) William Thomas Tutte (fr)
prop-fr:lieu	Cambridge (fr) Nagoya, Japon (fr) Université de Bordeaux I (fr)
prop-fr:lireEnLigne	http://tel.archives-ouvertes.fr/tel-00287330/en https://arxiv.org/pdf/1411.0737.pdf https://books.google.com/books%3Fid=X6xhj81Ro7EC&printsec=frontcover https://books.google.com/books%3Fid=pYfJe-ZVUyAC&printsec=frontcover https://books.google.com/books%3Fid=uTGhooU37h4C&printsec=frontcover https://www.math.upenn.edu/~wilf/AlgoComp.pdf
prop-fr:mathReviews	897317 (xsd:integer)
prop-fr:mr	586435 (xsd:integer) 1400247 (xsd:integer) 1667452 (xsd:integer) 2659710 (xsd:integer) 2738228 (xsd:integer)
prop-fr:natureOuvrage	thèse de doctorat en informatique (fr)
prop-fr:nom	Korn (fr) Lass (fr) Webb (fr) Martin (fr) Royle (fr) Welsh (fr) Haggard (fr) Merino (fr) Alon (fr) Awan (fr) Pearce (fr) Sokal (fr) Sinclair (fr) Goldberg (fr) Wilf (fr) Bernardi (fr) Jaeger (fr) Annan (fr) Chung (fr) Farr (fr) Biggs (fr) Bollobás (fr) Tani (fr) Husfeldt (fr) Tutte (fr) Pak (fr) Imai (fr) Sekine (fr) Björklund (fr) Yau (fr) Koivisto (fr) Kaski (fr) Fortuin (fr) Crapo (fr) Godsil (fr) Jerrum (fr) Kasteleyn (fr) Las Vergnas (fr) Vertigan (fr)
prop-fr:nomUrl	TuttePolynomial (fr)
prop-fr:numéro	1 (xsd:integer) 2 (xsd:integer) 3 (xsd:integer) 4 (xsd:integer) 5 (xsd:integer) 7 (xsd:integer) 8 (xsd:integer)
prop-fr:numéroArticle	R12 (fr)
prop-fr:numéroD'édition	2 (xsd:integer)
prop-fr:numéroDansCollection	34 (xsd:integer) 327 (xsd:integer) 1004 (xsd:integer)
prop-fr:page	Art. 24, 17 (fr) Article 6, 14 (fr)
prop-fr:pages	3 (xsd:integer) 5 (xsd:integer) 35 (xsd:integer) 181 (xsd:integer) 192 (xsd:integer) 210 (xsd:integer) 211 (xsd:integer) 231 (xsd:integer) 273 (xsd:integer) 367 (xsd:integer) 459 (xsd:integer) 536 (xsd:integer) 690 (xsd:integer) 908 (xsd:integer) 1087 (xsd:integer) 1101 (xsd:integer)
prop-fr:pagesTotales	163 (xsd:integer) 205 (xsd:integer) 333 (xsd:integer) 394 (xsd:integer) 439 (xsd:integer)
prop-fr:passage	28 (xsd:integer) 173 (xsd:integer) 224 (xsd:integer) 677 (xsd:integer) 839 (xsd:integer)
prop-fr:prénom	Fan (fr) Olivier (fr) Pierre (fr) Chris (fr) Gordon (fr) Michael (fr) Mikko (fr) C. (fr) J. D. (fr) Andreas (fr) Michel (fr) Hiroshi (fr) Mark (fr) N. (fr) Norman (fr) Igor (fr) F. (fr) Jordan (fr) David J. (fr) Gary (fr) Dirk (fr) W. T. (fr) Bodo (fr) Kyoko (fr) Alan D. (fr) D. L. (fr) Henry H. (fr) Alistair (fr) D. J. A. (fr) Béla (fr) Dominic J. A. (fr) Herbert S. (fr) Thore (fr) Graham E. (fr) Petteri (fr) Pieter W. (fr) Bridget S. (fr) Cees M. (fr) Leslie Ann (fr) S.-T. (fr) Seiichiro (fr)
prop-fr:sousTitre	Knots, Colourings and Counting (fr)
prop-fr:texte	orientations acycliques (fr) random cluster model (fr) rectangles parfaits (fr)
prop-fr:titre	Graph Theory (fr) Modern Graph Theory (fr) Complexity (fr) Algebraic Graph Theory (fr) Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (fr) A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs (fr) The Computational Complexity of Tutte Invariants for Planar Graphs (fr) Algorithms and complexity (fr) Combinatorial evaluations of the Tutte polynomial (fr) Computing Tutte Polynomials (fr) Computing Tutte polynomials (fr) Convexity in oriented matroids (fr) Coverings, heat kernels and spanning trees (fr) On the evaluation at of the Tutte polynomial of a graph (fr) Graph-polynomials (fr) Inapproximability of the Tutte polynomial (fr) Matroid Theory (fr) Edge-selection heuristics for computing Tutte polynomials (fr) The Potts model and the Tutte polynomial (fr) The Tutte polynomial (fr) Tilings of rectangles with T-tetrominoes (fr) Tutte polynomial (fr) Tutte polynomials for directed graphs (fr) On the random-cluster model: I. Introduction and relation to other models (fr) Combinatoire du polynôme de Tutte et des cartes planaires (fr) The Computational Complexity of the Tutte Plane: the Bipartite Case (fr) Orientations Acycliques et le Polynôme Chromatique (fr) On the computational complexity of the Jones and Tutte polynomials (fr) Computing the Tutte polynomial in vertex-exponential time (fr) Polynomial-time approximation algorithms for the Ising model (fr) The multivariate Tutte polynomial for graphs and matroids (fr) Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case (fr)
prop-fr:titreChapitre	Tutte-Whitney polynomials: some history and generalizations (fr) Computing the Tutte polynomial of a graph of moderate size (fr)
prop-fr:titreOuvrage	24 (xsd:integer) Surveys in Combinatorics (fr) Algorithms and computations (fr) Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (fr) Combinatorics, complexity, and chance. A tribute to Dominic Welsh (fr)
prop-fr:trad	Potts model (fr) Acyclic orientation (fr) Bollobás–Riordan polynomial (fr) Perfect rectangle (fr) Random cluster model (fr)
prop-fr:url	http://www.sciencedirect.com/science/article/pii/0095895680900829 http://www.sciencedirect.com/science/article/pii/0095895688900792 http://www.math.ucla.edu/~pak/papers/tutte7color.pdf http://cjtcs.cs.uchicago.edu/articles/2010/6/cats9-3-1.pdf https://dx.doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4%3C210::AID-RSA2%3E3.0.CO;2-R https://dx.doi.org/10.1017/S0963548300000195 https://dx.doi.org/10.1137/S0097539704446797 https://hal.archives-ouvertes.fr/hal-01283134 http://www.combinatorics.org/Volume_6/Abstracts/v6i1r12.html
prop-fr:volume	1 (xsd:integer) 3 (xsd:integer) 6 (xsd:integer) 15 (xsd:integer) 22 (xsd:integer) 29 (xsd:integer) 32 (xsd:integer) 35 (xsd:integer) 37 (xsd:integer) 41 (xsd:integer) 45 (xsd:integer) 57 (xsd:integer) 108 (xsd:integer) 140 (xsd:integer) 206 (xsd:integer) 319 (xsd:integer)
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Article_détaillé dbpedia-fr:Modèle:Autre4 dbpedia-fr:Modèle:Chapitre dbpedia-fr:Modèle:Citation_étrangère dbpedia-fr:Modèle:Début_de_colonnes dbpedia-fr:Modèle:Fin_de_colonnes dbpedia-fr:Modèle:Harvsp dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Traduction/Référence dbpedia-fr:Modèle:MathWorld dbpedia-fr:Modèle:Rouge dbpedia-fr:Modèle:Bleu dbpedia-fr:Modèle:Harv dbpedia-fr:Modèle:EncycloMath
prop-fr:zbl	1124.050200 (xsd:double)
prop-fr:éditeur	dbpedia-fr:Academic_Press dbpedia-fr:Cambridge_University_Press dbpedia-fr:Elsevier dbpedia-fr:John_Wiley_&_Sons dbpedia-fr:Oxford_University_Press dbpedia-fr:Prentice_Hall dbpedia-fr:Springer_Science+Business_Media dbpedia-fr:Université_Joseph-Fourier Labri (fr)
dct:subject	category-fr:Polynôme category-fr:Invariant_de_graphe category-fr:Combinatoire category-fr:Mathématiques_discrètes category-fr:Théorie_des_graphes
rdfs:comment	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é. (fr)
rdfs:label	Polynôme de Tutte (fr) Tutte polynomial (en)
rdfs:seeAlso	https://commons.wikimedia.org/wiki/Category:Tutte_polynomial http://mathworld.wolfram.com/TuttePolynomial.html https://www.quora.com/topic/Tutte-Polynomial
owl:sameAs	dbr:Tutte_polynomial dbpedia-commons:Category:Tutte_polynomial wikidata:Q7857002 dbpedia-ko:텃_다항식 dbpedia-ru:Многочлен_Татта http://g.co/kg/m/0b5fkz http://ma-graph.org/entity/14447369
prov:wasDerivedFrom	wikipedia-fr:Polynôme_de_Tutte?oldid=188761975&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Tractable_points_of_the_Tutte_polynomial_in_the_real_plane.svg wiki-commons:Special:FilePath/Tutte_polynomial_and_chromatic_polynomial_of_the_Bull_graph.jpg wiki-commons:Special:FilePath/Chromatic_in_the_Tutte_plane.jpg wiki-commons:Special:FilePath/Deletion-contraction.svg wiki-commons:Special:FilePath/Flow_in_the_Tutte_plane.jpg wiki-commons:Special:FilePath/Jones_in_the_Tutte_plane.jpg wiki-commons:Special:FilePath/Potts_and_Ising_in_the_Tutte_plane.jpg wiki-commons:Special:FilePath/Reliability_in_the_Tutte_plane.jpg
foaf:isPrimaryTopicOf	wikipedia-fr:Polynôme_de_Tutte
is dbo:wikiPageWikiLink of	dbpedia-fr:Orientation_forte dbpedia-fr:Physique_combinatoire dbpedia-fr:Théorie_algébrique_des_graphes dbpedia-fr:William_Tutte dbpedia-fr:Échelle_de_Möbius dbpedia-fr:Matrice_de_Tutte
is oa:hasTarget of	tag-fr:EnFrResource tag-fr:WdtFrResource
is foaf:primaryTopic of	wikipedia-fr:Polynôme_de_Tutte