| dbo:abstract |
En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. Le théorème de Robertson–Seymour est également appelé le théorème des mineurs, car le classement partiel évoqué dans son énoncé est défini par la relation « être un mineur ». Le théorème équivaut ainsi à dire que toute famille F de graphes fermée, c'est-à-dire telle que les mineurs des graphes de F appartiennent aussi à F, peut être caractérisée par un ensemble fini de « mineurs exclus ». Connu, avant qu'il soit démontré, sous le nom de conjecture de Wagner, ce théorème, démontré en 2004 par Neil Robertson et Paul Seymour, est considéré généralement comme un des résultats les plus importants de la théorie des graphes. Il a une démonstration extrêmement complexe et délicate, dont la publication, comportant plus de cinq cents pages, s'étale de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory. Le théorème n'est pas constructif (on ne connait d'ailleurs les listes explicites de mineurs exclus que dans très peu de cas), mais Robertson et Seymour ont montré qu'il a d'importantes conséquences en théorie de la complexité, car il garantit l'existence d'algorithmes rapides pour de nombreux problèmes de décision. (fr) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Konigsberg_bridges.png?width=300 |
| dbo:wikiPageExternalLink |
http://jacm.acm.org/ http://www.ams.org/journals/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf http://www.mrfellows.net/papers/FL89_Search,Decision,Efficiency.pdf http://perso.ens-lyon.fr/eric.thierry%7Ctitre=site http://perso.ens-lyon.fr/eric.thierry/Graphes2009/bastien-legloannec.pdf http://www.math.princeton.edu/~pds/papers/GM20/GM20.pdf http://www.math.princeton.edu/~pds/papers/GM21/GM21.pdf http://www.math.princeton.edu/~pds/papers/GM22/GM22.pdf http://www.math.princeton.edu/~pds/papers/GM23/GM23.pdf http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch12.pdf http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.56.4451&rep=rep1&type=pdf http://www.journals.elsevier.com/journal-of-computer-and-system-sciences/ http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf |
| dbo:wikiPageID |
5807231 (xsd:integer) |
| dbo:wikiPageLength |
60461 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
189636644 (xsd:integer) |
| dbo:wikiPageWikiLink |
category-fr:Théorème_de_la_théorie_des_graphes dbpedia-fr:Algorithme dbpedia-fr:American_Mathematical_Society dbpedia-fr:Andrew_Vázsonyi dbpedia-fr:Antichaîne dbpedia-fr:Arbre_(théorie_des_graphes) dbpedia-fr:Axiomes_de_Peano dbpedia-fr:Bel_ordre dbpedia-fr:Bruno_Courcelle category-fr:Théorème_d'informatique dbpedia-fr:Comparaison_asymptotique dbpedia-fr:Complexité_paramétrée dbpedia-fr:Complémentaire_(théorie_des_ensembles) dbpedia-fr:Conjecture dbpedia-fr:Contraction_d'arête dbpedia-fr:Coupe-cycles_de_sommets dbpedia-fr:Crispin_Nash-Williams dbpedia-fr:Croissance_exponentielle dbpedia-fr:Deuxième_cycle_universitaire dbpedia-fr:Décidabilité dbpedia-fr:Décomposition_arborescente dbpedia-fr:Démonstration_constructive dbpedia-fr:Ensemble_bien_ordonné dbpedia-fr:Ensemble_dénombrable dbpedia-fr:Ensemble_partiellement_ordonné dbpedia-fr:Ensembles_disjoints dbpedia-fr:Entrelacs_et_graphes dbpedia-fr:Genre_(mathématiques) dbpedia-fr:Giuseppe_Peano dbpedia-fr:Gottlob_Frege dbpedia-fr:Graphe_(mathématiques_discrètes) dbpedia-fr:Graphe_biparti_complet dbpedia-fr:Graphe_complet dbpedia-fr:Graphe_connexe dbpedia-fr:Graphe_cycle dbpedia-fr:Graphe_non_orienté dbpedia-fr:Graphe_planaire dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Graphe_toroïdal dbpedia-fr:Harvey_Friedman dbpedia-fr:Hypergraphe dbpedia-fr:Informatique_théorique dbpedia-fr:Isomorphisme dbpedia-fr:Jeff_Paris dbpedia-fr:Joseph_Kruskal dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Kazimierz_Kuratowski dbpedia-fr:Klaus_Wagner dbpedia-fr:Largeur_arborescente dbpedia-fr:Lemme_de_Higman dbpedia-fr:Leonhard_Euler dbpedia-fr:Lexique_de_la_théorie_des_graphes dbpedia-fr:Leçons_de_mathématiques_d'aujourd'hui dbpedia-fr:Logique_mathématique dbpedia-fr:Machine_de_Turing dbpedia-fr:Neil_Robertson_(mathématicien) dbpedia-fr:Nombre_cardinal dbpedia-fr:Négation_logique dbpedia-fr:Nœud_(mathématiques) dbpedia-fr:P_(complexité) dbpedia-fr:Paul_Seymour_(mathématicien) dbpedia-fr:Plan_(mathématiques) dbpedia-fr:Plan_projectif dbpedia-fr:Polyèdre dbpedia-fr:Pour_la_science dbpedia-fr:Prix_Fulkerson dbpedia-fr:Problème_NP-complet dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Problème_de_décision dbpedia-fr:Problème_des_sept_ponts_de_Königsberg dbpedia-fr:Problème_du_voyageur_de_commerce dbpedia-fr:Préordre dbpedia-fr:Raisonnement_par_récurrence dbpedia-fr:Relation_bien_fondée dbpedia-fr:Relation_binaire dbpedia-fr:Relation_d'ordre dbpedia-fr:Section_commençante dbpedia-fr:Suite_(mathématiques) dbpedia-fr:Surface_(géométrie_analytique) dbpedia-fr:Théorie_de_Ramsey dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Théorie_des_ensembles_de_Zermelo-Fraenkel dbpedia-fr:Théorie_des_graphes dbpedia-fr:Théorème dbpedia-fr:Théorème_de_Kruskal dbpedia-fr:Théorèmes_d'incomplétude_de_Gödel dbpedia-fr:Topologie dbpedia-fr:Tore dbpedia-fr:Union_(mathématiques) dbpedia-fr:Université_de_Victoria dbpedia-fr:École_normale_supérieure_de_Lyon dbpedia-fr:Énigme_des_trois_maisons dbpedia-fr:Fichier:7_bridges.svg dbpedia-fr:Fichier:Königsberg_graph.svg dbpedia-fr:Fichier:Toroidal_graph_sample.gif dbpedia-fr:Mathématiques dbpedia-fr:Maître_de_conférences dbpedia-fr:Mineur_(théorie_des_graphes) dbpedia-fr:Fichier:Petersen_family.svg dbpedia-fr:Fichier:Konigsberg_bridges.png dbpedia-fr:Fichier:Mineur.jpg |
| prop-fr:alignb |
center (fr) |
| prop-fr:année |
1983 (xsd:integer) 1987 (xsd:integer) 1988 (xsd:integer) 1994 (xsd:integer) 1995 (xsd:integer) 2002 (xsd:integer) 2004 (xsd:integer) 2005 (xsd:integer) 2008 (xsd:integer) 2010 (xsd:integer) |
| prop-fr:arrondi |
0.600000 (xsd:double) |
| prop-fr:auteursOuvrage |
S. Simpson (fr) |
| prop-fr:collection |
Contemporary Mathematics (fr) Handbooks in Operations Research and Management Science (fr) |
| prop-fr:couleurfondb |
transparent (fr) |
| prop-fr:couleurfondt |
transparent (fr) |
| prop-fr:date |
2011-12-21 (xsd:date) |
| prop-fr:doi |
10.100600 (xsd:double) 10.101600 (xsd:double) 10.114500 (xsd:double) |
| prop-fr:formatÉlectronique |
Pdf (fr) |
| prop-fr:fr |
Péter Komjáth (fr) |
| prop-fr:journal |
dbpedia-fr:Leçons_de_mathématiques_d'aujourd'hui dbpedia-fr:Pour_la_science http://jacm.acm.org/ http://www.journals.elsevier.com/journal-of-computer-and-system-sciences/ Bull. Amer. Math. Soc. (fr) Journal of Combinatorial Theory, Series B (fr) |
| prop-fr:lang |
en (fr) |
| prop-fr:langue |
en (fr) |
| prop-fr:largeur |
95.0 |
| prop-fr:lienAuteur |
Jean-Paul Delahaye (fr) |
| prop-fr:nom |
dbpedia-fr:Bruno_Courcelle Chambers (fr) Robertson (fr) Seymour (fr) Delahaye (fr) Friedman (fr) Bienstock (fr) Diestel (fr) Langston (fr) Fellows (fr) Lovász (fr) |
| prop-fr:numéro |
1 (xsd:integer) 2 (xsd:integer) 3 (xsd:integer) |
| prop-fr:numéroDansCollection |
7 (xsd:integer) 65 (xsd:integer) |
| prop-fr:oldid |
73333100 (xsd:integer) |
| prop-fr:pages |
39 (xsd:integer) 65 (xsd:integer) 75 (xsd:integer) 92 (xsd:integer) 167 (xsd:integer) 181 (xsd:integer) 325 (xsd:integer) 727 (xsd:integer) 769 (xsd:integer) |
| prop-fr:passage |
229 (xsd:integer) 326 (xsd:integer) 481 (xsd:integer) |
| prop-fr:prénom |
Paul (fr) Daniel (fr) Jean-Paul (fr) John (fr) Michael A. (fr) Harvey (fr) László (fr) Reinhard (fr) Neil (fr) Michael R. (fr) |
| prop-fr:titre |
Graph Minors. I. Excluding a forest (fr) Graph Minors. XX. Wagner's conjecture (fr) Graph Minor Theory (fr) Graph Minors. XXIII. Nash-Williams’s immersion conjecture (fr) Liste complète des vingt-trois articles de Robertson et Seymour (fr) Graph Minors. XIII. The disjoint paths problem (fr) Hunting for torus obstructions, M.Sc. thesis (fr) On search, decision, and the efficiency of polynomial-time algorithms (fr) Structuration des graphes et logique (fr) The metamathematics of the graph minor theorem (fr) Une propriété cachée des graphes (fr) Algorithmic implications of the graph minor theorem (fr) Nonconstructive tools for proving polynomial-time decidability (fr) |
| prop-fr:titreChapitre |
Minors, Trees, and WQO (fr) |
| prop-fr:titreOuvrage |
Graph Theory (fr) Logic and Combinatorics (fr) Network Models (fr) |
| prop-fr:url |
http://www.ams.org/journals/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf http://www.math.princeton.edu/~pds/papers/GM20/GM20.pdf http://www.math.princeton.edu/~pds/papers/GM23/GM23.pdf http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch12.pdf http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf http://perso.ens-lyon.fr/eric.thierry|titre=site professionnel de Eric Thierry (fr) |
| prop-fr:volume |
4 (xsd:integer) 35 (xsd:integer) 43 (xsd:integer) 49 (xsd:integer) 63 (xsd:integer) 92 (xsd:integer) 100 (xsd:integer) avril (fr) |
| prop-fr:wikiPageUsesTemplate |
dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Article_connexe dbpedia-fr:Modèle:Article_de_qualité dbpedia-fr:Modèle:Article_détaillé dbpedia-fr:Modèle:Chapitre dbpedia-fr:Modèle:Citation dbpedia-fr:Modèle:En dbpedia-fr:Modèle:En-tête_label dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Lien_web dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Pdf dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Traduction/Référence dbpedia-fr:Modèle:Retrait dbpedia-fr:Modèle:Boîte_déroulante/début dbpedia-fr:Modèle:Boîte_déroulante/fin dbpedia-fr:Modèle:Commentaire_biblio dbpedia-fr:Modèle:Théorème |
| prop-fr:éditeur |
dbpedia-fr:American_Mathematical_Society Springer (fr) Department of Computer Science, UVic (fr) |
| prop-fr:édition |
Electronic Edition 2005 (fr) |
| dct:subject |
category-fr:Théorème_de_la_théorie_des_graphes category-fr:Théorème_d'informatique |
| rdfs:comment |
En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. (fr) |
| rdfs:label |
Minorentheorem (de) Robertson–Seymour theorem (en) Teorema di Robertson-Seymour (it) Théorème de Robertson-Seymour (fr) |
| rdfs:seeAlso |
http://mathworld.wolfram.com/Robertson-SeymourTheorem.html |
| owl:sameAs |
dbr:Robertson–Seymour_theorem wikidata:Q3527155 dbpedia-de:Minorentheorem dbpedia-it:Teorema_di_Robertson-Seymour dbpedia-pt:Teorema_de_Robertson–Seymour dbpedia-ru:Теорема_Робертсона_—_Сеймура http://g.co/kg/m/01zcmv http://ma-graph.org/entity/173644813 |
| prov:wasDerivedFrom |
wikipedia-fr:Théorème_de_Robertson-Seymour?oldid=189636644&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/7_bridges.svg wiki-commons:Special:FilePath/Toroidal_graph_sample.gif wiki-commons:Special:FilePath/Complete_bipartite_graph_K3,3.svg wiki-commons:Special:FilePath/Complete_graph_K5.svg wiki-commons:Special:FilePath/Konigsberg_bridges.png wiki-commons:Special:FilePath/Königsberg_graph.svg wiki-commons:Special:FilePath/Mineur.jpg wiki-commons:Special:FilePath/Petersen_family.svg |
| foaf:isPrimaryTopicOf |
wikipedia-fr:Théorème_de_Robertson-Seymour |
| is dbo:wikiPageRedirects of |
dbpedia-fr:Conjecture_de_Wagner dbpedia-fr:Théorème_des_mineurs |
| is dbo:wikiPageWikiLink of |
dbpedia-fr:Conjecture_de_Wagner dbpedia-fr:Andrew_Vázsonyi dbpedia-fr:Bel_ordre dbpedia-fr:Combinatoire dbpedia-fr:Complexité_paramétrée dbpedia-fr:Contraction_d'arête dbpedia-fr:Critère_de_planarité_de_Mac_Lane dbpedia-fr:Famille_de_Petersen dbpedia-fr:Graphe_cactus dbpedia-fr:Graphe_planaire dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Graphe_toroïdal dbpedia-fr:Histoire_des_mathématiques dbpedia-fr:Homéomorphisme_de_graphes dbpedia-fr:Invariant_de_Colin_de_Verdière dbpedia-fr:Jim_Geelen dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Julia_Chuzhoy dbpedia-fr:Klaus_Wagner dbpedia-fr:Lemme_de_Higman dbpedia-fr:Liste_de_conjectures_mathématiques dbpedia-fr:Liste_de_théorèmes dbpedia-fr:Longueur_d'une_démonstration dbpedia-fr:Neil_Robertson_(mathématicien) dbpedia-fr:Paul_Seymour_(mathématicien) dbpedia-fr:Prix_Fulkerson dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Pseudo-forêt dbpedia-fr:Rudolf_Halin dbpedia-fr:Théorie_des_graphes dbpedia-fr:Théorème_d'accélération_de_Gödel dbpedia-fr:Théorème_de_Courcelle dbpedia-fr:Théorème_de_Kruskal dbpedia-fr:Énigme_des_trois_maisons dbpedia-fr:Théorème_des_mineurs dbpedia-fr:Mineur_(théorie_des_graphes) |
| is oa:hasTarget of |
tag-fr:DeFrResource tag-fr:EnFrResource tag-fr:ItFrResource tag-fr:WdtFrResource |
| is foaf:primaryTopic of |
wikipedia-fr:Théorème_de_Robertson-Seymour |
