Abstract:
Dans ce mémoire, nous nous intéressons à abordé certainement l’un des plus fameux
sujets de la théorie des graphes ; le parcours lexicographique et les graphe parfaits, en
particulier les graphes triangulés, nous parlons de quelques problèmes d’optimisation
dans les graphes triangulés résolus par lexbfs afin d’obtenir des meilleurs résultats.
Après avoir montré quel genre de résultat nous pouvions attendre, nous étudions
comment adapter les méthodes connus à ce jour à savoir l’algorithme color, lexbfs color. . .
etc pour la résolution des problèmes concrets, les limites de ces algorithmes sont utilisés
dans le cadre de l’optimisation
