Théorème des graphes parfaits

Théorème des graphes parfaits

Le graphe parfait est une notion introduite par Claude Berge, dont les conjectures ont été démontrées en 1972 et 2002 et sont devenues des théorèmes.

Sommaire

Contexte

Dans le cadre de la théorie des graphes, Claude Berge a introduit en 1960 la notion de graphe parfait comme définissant un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux.

Théorèmes

Il a proposé deux conjectures de caractérisation de ces graphes parfaits, élevées au rang de théorèmes depuis leur démonstration :

  • Théorème faible des graphes parfaits :
Un graphe est parfait si et seulement si son complémentaire est parfait.

Cette conjecture a été démontrée en 1972 par László Lovász.

  • Théorème fort des graphes parfaits :
Un graphe est parfait si et seulement si ni lui ni son complémentaire ne contiennent de cycle impair induit de longueur au moins cinq.

Cette conjecture a été démontrée en 2002 par Maria Chudnovsky (en), Neil Robertson, Paul Seymour et Robin Thomas (en).

Remarque

Le théorème fort implique trivialement le théorème faible. De fait on parle du « théorème des graphes parfaits » en désignant implicitement le théorème fort.

Intérêt

Depuis la formulation des conjectures jusqu'à la démonstration du théorème fort, l'intérêt pour les graphes parfaits n'a cessé de croitre. Il n'est pas retombé non plus après la publication de la preuve puisque la très grande technicité et la longueur de celle-ci laissent espérer l'existence d'une preuve plus courte et qui renforce la compréhension.

Les deux principales motivations, en dehors de la théorie des graphes, pour l'étude des graphes parfaits sont d'ordres polyédral et algorithmique. Ceci tient notamment à l'existence d'une autre définition équivalente d'un graphe parfait due à Václav Chvátal (en)[1] :

Un graphe est parfait si et seulement si son polytope des stables est défini par les contraintes de clique.

Partant de ce résultat, Martin Grötschel (en), László Lovász et Alexander Schrijver (en) montrent que l'on peut résoudre en temps polynomial le problème de la coloration de graphe[2], équivalent au problème de la recherche du stable maximum – et aussi au problème de la recherche de la clique maximum, par le théorème faible.

Notes

  1. Václav Chvátal : On certain polytopes associated with graphs. Journal of Combinatorial Theory B 18 (1975), 138–154.
  2. Martin Grötschel, László Lovász et Alexander Schrijver : Geometric algorithms and combinatorial optimization. Springer-Verlag (1988, 362 pages) (ISBN 0-387-13624-X) et (2nd corrected edition, 1993) (ISBN 978-0-387-56740-2).

Références

  • Claude Berge, « Graphes et hypergraphes », Dunod, 2e édition, 1973 (en particulier, chapitre 16 sur les graphes parfaits) — (ISBN 2-04-016906-7).
  • Claude Berge, « Graphes », Gauthier-Villars, 3e édition, 1983 — (ISBN 2-04-015555-4).
  • László Lovász, « Normal hypergraphs and the perfect graph conjecture », Discrete Math. 2, 253-267, 1972.
  • Maria Chudnovsky, Neil Robertson, Paul D. Seymour et Robin Thomas, « Progress on perfect graphs », Math. Programming Ser. B 97, 405-422, 2003 PDF.

Liens internes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème des graphes parfaits de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Theoreme des graphes parfaits — Théorème des graphes parfaits Sommaire 1 Contexte 2 Théorèmes 3 Intérêt 4 Notes 5 Références …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theoreme quatre couleurs — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste Des Théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

  • Liste des theoremes — Liste des théorèmes Liste des théorèmes par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le… …   Wikipédia en Français

  • Liste des théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”