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.

PropertyValue
dbpedia-owl: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. Le théorème de Robertson–Seymour 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'étala de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory.Le théorème en lui-mê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 avait 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.
  • In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 and the complete bipartite graph K3,3 as minors.The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it.A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal and S. Tarkowski.
  • Das Minorentheorem gilt als einer der tiefgreifensten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung.
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 5807231 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 60205 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 156 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 110845873 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
prop-fr:alignb
  • center
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
prop-fr:collection
  • Contemporary Mathematics
  • Handbooks in Operations Research and Management Science
prop-fr:colonnes
  • 2 (xsd:integer)
prop-fr:contribution
  • Minors, Trees, and WQO
prop-fr:couleurfondb
  • transparent
prop-fr:couleurfondt
  • transparent
  • transparent
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:edition
  • Electronic Edition 2005
prop-fr:groupe
  • "note"
prop-fr:issue
  • 1 (xsd:integer)
  • 2 (xsd:integer)
  • 3 (xsd:integer)
prop-fr:journal
prop-fr:lang
  • en
prop-fr:largeur
  • 95.0
prop-fr:lienAuteur
  • Jean-Paul Delahaye
prop-fr:nom
  • Chambers
  • Friedman
  • Bienstock
  • Delahaye
  • Robertson
  • Seymour
  • Lovász
  • Langston
  • Fellows
  • Diestel
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
  • Daniel
  • Harvey
  • Jean-Paul
  • John
  • László
  • Michael A.
  • Michael R.
  • Neil
  • Paul
  • Reinhard
prop-fr:titre
  • Graph Minor Theory
  • Graph Minors. I. Excluding a forest
  • Graph Theory
  • Graph Minors. XXIII. Nash-Williams’s immersion conjecture
  • Graph Minors. XIII. The disjoint paths problem
  • Graph Minors. XX. Wagner's conjecture
  • Hunting for torus obstructions, M.Sc. thesis
  • On search, decision, and the efficiency of polynomial-time algorithms
  • Structuration des graphes et logique
  • The metamathematics of the graph minor theorem
  • Une propriété cachée des graphes
  • Algorithmic implications of the graph minor theorem
  • La liste complète des vingt-trois articles de Robertson et Seymour
  • site professionnel de Eric Thierry
  • Nonconstructive tools for proving polynomial-time decidability
prop-fr:titreOuvrage
  • Logic and Combinatorics
  • Network Models
prop-fr:url
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
prop-fr:wikiPageUsesTemplate
prop-fr:éditeur
dcterms:subject
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.
  • In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.
  • Das Minorentheorem gilt als einer der tiefgreifensten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”.
rdfs:label
  • Théorème de Robertson-Seymour
  • Minorentheorem
  • Robertson–Seymour theorem
owl:sameAs
http://www.w3.org/ns/prov#wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of