Calcul D'invariants Dans Les Graphes Parfaits
Résumé: Nous avons vu que la classe des graphes parfaits était une classe de graphes importantes, en particulier parce qu'elle contient de nombreuses autre classes usuelles, dont les graphes d'intervalles, les graphes de comparabilité ou les graphes triangulés. On peut penser que la preuve des deux conjectures posées par Berge au début des années 1960 clôt la discussion au sujet des graphes parfaits, car cette classe est désormais trés bien connue. P. Seymour mentionne dans un premier axe de recherche, qui consisterait à améliorer la preuve du théorème fort des graphes parfaits. Un autre axe, qui semble a priori plus intéressant, serait d'obtenir un algorithme de construction explicite des graphes de Berge. Dans le même axe, on sait qu'il existe un algorithme de coloriage polynômial, à base de polyèdres et de programmation linéaire : mais existe-t-il un algorithme combinatoire, plus proche de la structure des graphes parfaits
Mots-clès:
Nos services universitaires et académiques
Thèses-Algérie vous propose ses divers services d’édition: mise en page, révision, correction, traduction, analyse du plagiat, ainsi que la réalisation des supports graphiques et de présentation (Slideshows).
Obtenez dès à présent et en toute facilité votre devis gratuit et une estimation de la durée de réalisation et bénéficiez d'une qualité de travail irréprochable et d'un temps de livraison imbattable!
Aucun fichier associé
Si le fichier est volumineux, l'affichage peut échouer. Vous pouvez obtenir le fichier directement en cliquant sur le bouton "Télécharger".
