This HTML5 document contains 274 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n27http://www.ams.org/journals/bull/2006-43-01/S0273-0979-05-01088-8/
dbrhttp://dbpedia.org/resource/
n36http://www.math.princeton.edu/~pds/papers/GM22/
n12http://fr.dbpedia.org/resource/Modèle:
n22http://www.cs.utk.edu/~langston/courses/cs594-fall2003/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
n33http://www.mrfellows.net/papers/
dcthttp://purl.org/dc/terms/
n31http://www.math.princeton.edu/~pds/papers/GM20/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n30http://g.co/kg/m/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://fr.dbpedia.org/resource/Fichier:
xsdhhttp://www.w3.org/2001/XMLSchema#
n28http://fr.dbpedia.org/resource/Modèle:Traduction/
n20http://ma-graph.org/entity/
n25http://citeseerx.ist.psu.edu/viewdoc/
prop-frhttp://fr.dbpedia.org/property/
dbohttp://dbpedia.org/ontology/
n32http://mathworld.wolfram.com/
dbpedia-pthttp://pt.dbpedia.org/resource/
n29http://www.math.princeton.edu/~pds/papers/GM23/
n11http://perso.ens-lyon.fr/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n14http://jacm.acm.org/
n35http://www.math.princeton.edu/~pds/papers/GM21/
n13http://perso.ens-lyon.fr/eric.thierry/Graphes2009/
n18http://www.journals.elsevier.com/journal-of-computer-and-system-sciences/
n6http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/
dbpedia-ithttp://it.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
wikipedia-frhttp://fr.wikipedia.org/wiki/
n37http://fr.dbpedia.org/resource/Modèle:Boîte_déroulante/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbpedia-fr:Théorème_de_Robertson-Seymour
rdfs:label
Minorentheorem Robertson–Seymour theorem Teorema di Robertson-Seymour Théorème de Robertson-Seymour
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.
rdfs:seeAlso
n32:Robertson-SeymourTheorem.html
owl:sameAs
dbpedia-de:Minorentheorem dbpedia-ru:Теорема_Робертсона_—_Сеймура n20:173644813 dbpedia-pt:Teorema_de_Robertson–Seymour wikidata:Q3527155 n30:01zcmv dbpedia-it:Teorema_di_Robertson-Seymour dbr:Robertson–Seymour_theorem
dbo:wikiPageID
5807231
dbo:wikiPageRevisionID
189636644
dbo:wikiPageWikiLink
n5:Toroidal_graph_sample.gif dbpedia-fr:Graphe_connexe dbpedia-fr:Graphe_complet dbpedia-fr:Surface_(géométrie_analytique) n5:Petersen_family.svg dbpedia-fr:Coupe-cycles_de_sommets dbpedia-fr:Croissance_exponentielle dbpedia-fr:Mathématiques dbpedia-fr:Graphe_biparti_complet dbpedia-fr:Pour_la_science n5:Mineur.jpg dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Problème_NP-complet dbpedia-fr:Algorithme dbpedia-fr:Journal_of_Combinatorial_Theory dbpedia-fr:Préordre dbpedia-fr:Tore dbpedia-fr:Kazimierz_Kuratowski dbpedia-fr:Ensemble_bien_ordonné dbpedia-fr:Raisonnement_par_récurrence dbpedia-fr:Graphe_toroïdal dbpedia-fr:Démonstration_constructive dbpedia-fr:American_Mathematical_Society n5:Konigsberg_bridges.png dbpedia-fr:Plan_(mathématiques) dbpedia-fr:Bel_ordre dbpedia-fr:Lexique_de_la_théorie_des_graphes dbpedia-fr:Jeff_Paris dbpedia-fr:Théorie_des_graphes dbpedia-fr:Section_commençante dbpedia-fr:Ensembles_disjoints dbpedia-fr:Lemme_de_Higman dbpedia-fr:Giuseppe_Peano dbpedia-fr:École_normale_supérieure_de_Lyon dbpedia-fr:P_(complexité) dbpedia-fr:Théorie_des_ensembles_de_Zermelo-Fraenkel dbpedia-fr:Théorèmes_d'incomplétude_de_Gödel dbpedia-fr:Théorie_de_Ramsey dbpedia-fr:Andrew_Vázsonyi dbpedia-fr:Nœud_(mathématiques) dbpedia-fr:Graphe_(mathématiques_discrètes) dbpedia-fr:Joseph_Kruskal dbpedia-fr:Paul_Seymour_(mathématicien) dbpedia-fr:Maître_de_conférences dbpedia-fr:Problème_du_voyageur_de_commerce dbpedia-fr:Plan_projectif dbpedia-fr:Genre_(mathématiques) dbpedia-fr:Leonhard_Euler dbpedia-fr:Ensemble_partiellement_ordonné dbpedia-fr:Union_(mathématiques) dbpedia-fr:Isomorphisme dbpedia-fr:Prix_Fulkerson dbpedia-fr:Crispin_Nash-Williams dbpedia-fr:Suite_(mathématiques) dbpedia-fr:Décidabilité dbpedia-fr:Théorème_de_Kruskal dbpedia-fr:Graphe_planaire_extérieur dbpedia-fr:Deuxième_cycle_universitaire dbpedia-fr:Graphe_planaire dbpedia-fr:Arbre_(théorie_des_graphes) dbpedia-fr:Gottlob_Frege dbpedia-fr:Graphe_non_orienté dbpedia-fr:Neil_Robertson_(mathématicien) dbpedia-fr:Informatique_théorique dbpedia-fr:Négation_logique dbpedia-fr:Complémentaire_(théorie_des_ensembles) dbpedia-fr:Mineur_(théorie_des_graphes) category-fr:Théorème_de_la_théorie_des_graphes dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Université_de_Victoria dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Problème_des_sept_ponts_de_Königsberg dbpedia-fr:Machine_de_Turing dbpedia-fr:Énigme_des_trois_maisons dbpedia-fr:Polyèdre dbpedia-fr:Conjecture dbpedia-fr:Leçons_de_mathématiques_d'aujourd'hui dbpedia-fr:Théorème dbpedia-fr:Harvey_Friedman dbpedia-fr:Complexité_paramétrée dbpedia-fr:Klaus_Wagner dbpedia-fr:Décomposition_arborescente dbpedia-fr:Antichaîne dbpedia-fr:Bruno_Courcelle dbpedia-fr:Axiomes_de_Peano dbpedia-fr:Hypergraphe dbpedia-fr:Problème_de_décision n5:Königsberg_graph.svg dbpedia-fr:Entrelacs_et_graphes dbpedia-fr:Nombre_cardinal category-fr:Théorème_d'informatique dbpedia-fr:Ensemble_dénombrable dbpedia-fr:Relation_d'ordre dbpedia-fr:Comparaison_asymptotique dbpedia-fr:Topologie dbpedia-fr:Largeur_arborescente dbpedia-fr:Relation_bien_fondée dbpedia-fr:Relation_binaire dbpedia-fr:Logique_mathématique dbpedia-fr:Graphe_cycle dbpedia-fr:Contraction_d'arête n5:7_bridges.svg
dbo:wikiPageExternalLink
n11:eric.thierry%7Ctitre=site n13:bastien-legloannec.pdf n6:Ch12.pdf n18: n25:download%3Fdoi=10.1.1.56.4451&rep=rep1&type=pdf n14: n33:FL89_Search,Decision,Efficiency.pdf n31:GM20.pdf n35:GM21.pdf n36:GM22.pdf n29:GM23.pdf n22:BL.pdf n27:S0273-0979-05-01088-8.pdf
dbo:wikiPageLength
60461
dct:subject
category-fr:Théorème_d'informatique category-fr:Théorème_de_la_théorie_des_graphes
prop-fr:wikiPageUsesTemplate
n12:Lien n12:, n12:Lien_web n12:Retrait n12:Ouvrage n12:Pdf n12:Article_connexe n12:Article n12:Chapitre n12:Citation n12:Références n12:Portail n12:Article_de_qualité n12:Article_détaillé n12:Commentaire_biblio n28:Référence n12:Théorème n37:fin n12:En n12:En-tête_label n37:début
prov:wasDerivedFrom
wikipedia-fr:Théorème_de_Robertson-Seymour?oldid=189636644&ns=0
foaf:depiction
n10:7_bridges.svg n10:Mineur.jpg n10:Königsberg_graph.svg n10:Complete_bipartite_graph_K3,3.svg n10:Petersen_family.svg n10:Toroidal_graph_sample.gif n10:Complete_graph_K5.svg n10:Konigsberg_bridges.png
prop-fr:année
1987 1988 1994 1995 2002 2004 2005 2010 2008 1983
prop-fr:collection
Contemporary Mathematics Handbooks in Operations Research and Management Science
prop-fr:date
2011-12-21
prop-fr:doi
10.1006 10.1145 10.1016
prop-fr:fr
Péter Komjáth
prop-fr:journal
n14: dbpedia-fr:Leçons_de_mathématiques_d'aujourd'hui Journal of Combinatorial Theory, Series B Bull. Amer. Math. Soc. n18: dbpedia-fr:Pour_la_science
prop-fr:lang
en
prop-fr:langue
en
prop-fr:lienAuteur
Jean-Paul Delahaye
prop-fr:nom
Seymour Lovász dbpedia-fr:Bruno_Courcelle Chambers Robertson Bienstock Diestel Fellows Langston Friedman Delahaye
prop-fr:numéro
2 3 1
prop-fr:oldid
73333100
prop-fr:pages
769 39 92 75 65 325 181 167 727
prop-fr:passage
229 481 326
prop-fr:prénom
Michael A. Jean-Paul John László Michael R. Daniel Paul Harvey Neil Reinhard
prop-fr:titre
On search, decision, and the efficiency of polynomial-time algorithms Graph Minors. XXIII. Nash-Williams’s immersion conjecture Nonconstructive tools for proving polynomial-time decidability Graph Minor Theory Hunting for torus obstructions, M.Sc. thesis The metamathematics of the graph minor theorem Structuration des graphes et logique Graph Minors. XX. Wagner's conjecture Algorithmic implications of the graph minor theorem Une propriété cachée des graphes Liste complète des vingt-trois articles de Robertson et Seymour Graph Minors. XIII. The disjoint paths problem Graph Minors. I. Excluding a forest
prop-fr:titreChapitre
Minors, Trees, and WQO
prop-fr:titreOuvrage
Network Models Logic and Combinatorics Graph Theory
prop-fr:url
http://perso.ens-lyon.fr/eric.thierry|titre=site professionnel de Eric Thierry n6:Ch12.pdf n22:BL.pdf n27:S0273-0979-05-01088-8.pdf n29:GM23.pdf n31:GM20.pdf
prop-fr:volume
49 63 35 43 avril 92 100 4
prop-fr:éditeur
dbpedia-fr:American_Mathematical_Society Springer Department of Computer Science, UVic
prop-fr:alignb
center
prop-fr:auteursOuvrage
S. Simpson
prop-fr:couleurfondb
transparent
prop-fr:couleurfondt
transparent
prop-fr:formatÉlectronique
Pdf
prop-fr:largeur
95.0
prop-fr:numéroDansCollection
65 7
prop-fr:édition
Electronic Edition 2005
prop-fr:arrondi
0.6
dbo:thumbnail
n10:Konigsberg_bridges.png?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Théorème_de_Robertson-Seymour
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.