| Property |
Value |
| 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)
- 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 60461 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:alignb
| |
| 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
| |
| prop-fr:auteursOuvrage
|
- S. Simpson (fr)
- S. Simpson (fr)
|
| prop-fr:collection
|
- Contemporary Mathematics (fr)
- Handbooks in Operations Research and Management Science (fr)
- Contemporary Mathematics (fr)
- Handbooks in Operations Research and Management Science (fr)
|
| prop-fr:couleurfondb
|
- transparent (fr)
- transparent (fr)
|
| prop-fr:couleurfondt
|
- transparent (fr)
- transparent (fr)
|
| prop-fr:date
| |
| prop-fr:doi
|
- 10.100600 (xsd:double)
- 10.101600 (xsd:double)
- 10.114500 (xsd:double)
|
| prop-fr:formatÉlectronique
| |
| prop-fr:fr
|
- Péter Komjáth (fr)
- Péter Komjáth (fr)
|
| prop-fr:journal
| |
| prop-fr:lang
| |
| prop-fr:langue
| |
| prop-fr:largeur
| |
| prop-fr:lienAuteur
|
- Jean-Paul Delahaye (fr)
- 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
| |
| 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)
- 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)
- 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)
- Minors, Trees, and WQO (fr)
|
| prop-fr:titreOuvrage
|
- Graph Theory (fr)
- Logic and Combinatorics (fr)
- Network Models (fr)
- Graph Theory (fr)
- Logic and Combinatorics (fr)
- Network Models (fr)
|
| 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 (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| prop-fr:édition
|
- Electronic Edition 2005 (fr)
- Electronic Edition 2005 (fr)
|
| dct: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. 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)
- 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
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
