Bibliothèque Tangente. N° 54. Le théorème des mineurs. p. 44-49.
Auteur : Delahaye Jean-Paul
Résumé
Le théorème des mineurs ou théorème de Robertson-Seymour a été énoncé en 1937 par Klaus Wagner et démontré en 2004 par Neil Robertson et Paul Seymour. L’auteur de cet article en énonce deux formes. S’il ne peut en donner la démonstration, qui a nécessité 500 pages de raisonnement et de calculs, il explique en détail ce qu’est un mineur, ce que sont un ensemble stable par minoration et l’ensemble d’obstruction d’un graphe et montre la portée de ce théorème dont la démonstration n’est pas constructive en algorithmique.
Notes
Cet article est publié sous la rubrique « Savoirs ».
Il fait partie du dossier : Les types de graphes dans Bibliothèque Tangente n° 54 – Les graphes.
Il est également paru dans Tangente Hors-série n° 54 – Les graphes.
Données de publication
Éditeur Editions POLE Paris , 2015 Collection Bibliothèque Tangente Num. 54 Format 17 cm x 24 cm, p. 44-49
ISBN 2-84884-136-2 EAN 9782848841366 ISSN 2263-4908
Public visé élève ou étudiant, enseignant, tout public Niveau 1re, 2de, licence, lycée, terminale Âge 15, 16, 17, 18, 19
Type chapitre d’un ouvrage, vulgarisation, popularisation Langue français Support papier
Classification