Wikipédia

Théorème des graphes parfaits

caractérisation des graphes parfaits

En mathématiques, et plus précisément en théorie des graphes, le théorème des graphes parfaits (parfois appelé théorème fort des graphes parfaits) est une caractérisation des graphes parfaits par certains sous-graphes exclus (en), conjecturée par Claude Berge en 1961. Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas en annoncèrent la démonstration en 2002[1], et la publièrent en 2006. Elle valut à leurs auteurs le prix Fulkerson de 2009[2].

Définitions et énoncé du théorème modifier

On appelle sous-graphe induit par un certain ensemble de sommets d'un graphe G le graphe formé de ces sommets et des arêtes de G les reliant ; une clique est un sous-graphe induit isomorphe à un graphe complet, c'est-à-dire que tous les sommets sont connectés ; le nombre de clique d'un graphe est le nombre de sommets de sa plus grande clique. Le nombre chromatique d'un graphe est le plus petit nombre de couleurs nécessaire pour qu'il existe une coloration de ce graphe, c'est-à-dire une fonction associant à chaque sommet du graphe une couleur, de telle sorte que deux sommets reliés par une arête aient des couleurs différentes (le nombre chromatique est toujours supérieur ou égal au nombre de clique). Enfin, le graphe complémentaire de G est le graphe ayant les mêmes sommets que G, et dans lequel deux sommets sont reliés si et seulement si ils ne le sont pas dans G.

Avec ces définitions, un graphe parfait est un graphe pour lequel chaque sous-graphe induit a un nombre de clique égal à son nombre chromatique.

De nombreuses classes de graphes sont parfaits, par exemple les graphes bipartis, les graphes cordaux, et les graphes de comparabilité. Dans des travaux de 1961 et 1963 où il définissait pour la première fois ces graphes, Claude Berge remarquait qu'un graphe parfait ne peut contenir de trou impair, c'est-à-dire de graphe induit qui soit un cycle d'ordre impair supérieur à 5, car ceux-ci ont 2 pour nombre de clique et 3 pour nombre chromatique. De même, un graphe parfait ne peut contenir un antitrou impair (c'est-à-dire un trou du graphe complémentaire) car un antitrou de 2k + 1 sommets a k pour nombre de clique et k + 1 pour nombre chromatique (si k > 1). Les graphes n'ayant ni trous, ni antitrous furent appelés des graphes de Berge.

Berge conjectura que ces graphes étaient tous parfaits (et donc que les graphes de Berge s'identifiaient aux graphes parfaits), ce qui fut appelé la conjecture (forte) des graphes parfaits, jusqu'à sa démonstration en 2002, où elle devint le

Théorème des graphes parfaits — Un graphe est parfait si et seulement si ni lui, ni son complémentaire ne contient de sous-graphe induit qui soit un cycle d'ordre impair ≥ 5.

Cette caractérisation s'appliquant identiquement à un graphe et à son complémentaire, il en résulte immédiatement le résultat plus faible suivant :

Théorème faible des graphes parfaits — Si un graphe est parfait, son complémentaire est également parfait.

Ce dernier résultat, conjecturé également par Claude Berge, fut démontré en 1972 par László Lovász. Le théorème des graphes parfaits est, pour cette raison, parfois connu sous le nom de théorème fort des graphes parfaits.

Esquisse de la démonstration modifier

La démonstration du théorème par Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas (en 2002) suit un schéma conjecturé en 2001 par Conforti, Gérard Cornuéjols, Robertson, Seymour et Thomas, selon lequel tout graphe de Berge est composé de graphes plus simples au moyen de quatre constructions distinctes, se ramenant finalement à des graphes parfaits de cinq types possibles. Un graphe de Berge imparfait minimal ne peut être ainsi décomposé, ce qui montre qu'un contre-exemple au théorème est impossible[3]. Ce plan d'attaque reprend une conjecture antérieure de décomposition structurale qui s'était avérée erronée[4].

Les cinq classes de graphes parfaits modifier

Les cinq classes de graphes parfaits servant de base à ces décompositions structurales sont les graphes bipartis, les graphes adjoints des graphes bipartis, les graphes complémentaires des graphes bipartis et de leurs graphes adjoints, et les graphes « doublement séparés »[5]. On voit facilement que les graphes bipartis sont parfaits : tout sous-graphe induit non trivial a 2 pour nombre chromatique et pour nombre de clique. La perfection des complémentaires des graphes bipartis et des complémentaires de leurs graphes adjoints sont toutes deux équivalentes au théorème de Kőnig reliant les tailles des couplages maximaux, du stable maximum, et de la couverture minimale pour les graphes bipartis. La perfection des graphes adjoints aux graphes bipartis est équivalente à ce que ces derniers sont d'indice chromatique égal à leur degré maximum, résultat démontré lui aussi par Kőnig[6]. On montre que les graphes « doublement séparés » sont eux aussi parfaits[7].

Les quatre décompositions modifier

Les quatre types de décompositions utilisés dans la démonstration sont les 2-jonctions et leurs complémentaires, les partitions antisymétriques équilibrées, et les paires homogènes (en 2006, Chudnovsky simplifia la démonstration du théorème des graphes parfaits en montrant que les décompositions en paires homogènes pouvaient être éliminées de cette liste[8]).

Une 2-jonction est une partition des sommets d'un graphe en deux sous-ensembles tels que les arêtes reliant l'un à l'autre forment deux graphes bipartis complets sans sommets communs. Un graphe admettant une 2-jonction peut être décomposé en deux sous-graphes induits appelés blocs en remplaçant un des deux sous-ensembles par un chemin minimal de cet ensemble connectant l'un des graphes bipartis complets à l'autre[9], et le graphe est parfait si et seulement si les deux blocs sont parfaits. Ainsi, un graphe imparfait minimal ayant une 2-jonction s'identifie à un de ses blocs ; on montre alors que ce bloc est un cycle d'ordre impair et donc que le graphe n'est pas un graphe de Berge ; le même raisonnement permet de montrer qu'un graphe imparfait minimal dont le complémentaire admet une 2-jonction n'est pas un graphe de Berge[10].

Une partition antisymétrique (en) est une partition des sommets du graphe en deux sous-ensembles induisant respectivement un sous-graphe non connexe et le complémentaire d'un sous-graphe ; Chvátal a conjecturé qu'un graphe de Berge imparfait minimal ne pouvait admettre de partition antisymétrique[11]. Chudnovsky introduisit quelques contraintes techniques supplémentaires, démontrant ainsi la conjecture de Chvátal pour les partitions antisymétriques « équilibrées »[12].

Une paire homogène est une sorte de décomposition modulaire (en) d'un graphe. C'est une partition du graphe en trois sous-ensembles de sommets, V1, V2 et V3, tels que V1 et V2 ont ensemble au moins trois sommets et V3 au moins deux sommets, et que pour chaque sommet v de V3 et chaque i de {1,2}, ou bien v est adjacent à tous les sommets de Vi, ou bien il ne l'est à aucun. Un graphe de Berge imparfait minimal ne peut posséder de paire homogène[13].

Démonstration de l'existence d'une décomposition modifier

La démonstration de ce que tout graphe de Berge admet une des quatre décompositions (ou est d'un des cinq types de base) suit une analyse par décomposition en cas, selon la présence de certaines configurations dans le graphe : un extenseur, sous-graphe pouvant être décomposé en trois chemins induits (avec certaines contraintes supplémentaires), le complémentaire d'un extenseur, ou enfin une roue propre, configuration proche d'un graphe roue, formée d'un cycle induit et d'un sommet « moyeu » adjacent à au moins trois sommets du cycle (avec certaines contraintes supplémentaires). Tout graphe de Berge contient au moins une de ces trois configurations, et pour chacun de ces trois cas, on montre qu'il est décomposable[14] ; ceci achève la démonstration du théorème.

Notes modifier

  1. ↑ Mackenzie 2002 ; Cornuéjols 2002.
  2. ↑ (en) « 2009 Fulkerson Prizes », Notices Amer. Math. Soc.,‎ , p. 1475-1476 (lire en ligne).
  3. ↑ Cornuéjols 2002, conjecture 5.1.
  4. ↑ Reed 1986 ; Hougardy 1991 ; Rusu 1997 ; Roussel, Rusu et Thuillier 2009, section 4.6 « The first conjectures ».
  5. ↑ Ou « doublement scindés ». Voir l'article graphe scindé pour une définition rigoureuse de ces graphes.
  6. ↑ Kőnig 1916
  7. ↑ Roussel, Rusu et Thuillier 2009, définition 4.39.
  8. ↑ Chudnovsky 2006
  9. ↑ S'il n'existe pas de tel chemin, le bloc est formé en remplaçant le sous-ensemble par deux sommets, correspondant aux deux graphes bipartis.
  10. ↑ Cornuéjols et Cunningham 1985 ; Cornuéjols 2002, théorème 3.2 et corollaire 3.3.
  11. ↑ Chvátal 1985
  12. ↑ Seymour 2006 ; Roussel, Rusu et Thuillier 2009, section 4.7 « The skew partition » ; Cornuéjols 2002, théorèmes 4.1 et 4.2.
  13. ↑ Chvátal et Sbihi 1987 ; Cornuéjols 2002, théorème 4.10.
  14. ↑ Cornuéjols 2002, théorèmes 5.4, 5.5, et 5.6 ; Roussel, Rusu et Thuillier 2009, théorème 4.42.

Références modifier

Liens externes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Théorème_des_graphes_parfaits&oldid=210247082 ».