Sur des généralisations des graphes triangulés (application aux problèmes de satisfaction de contraintes)

Le cadre de cette thèse est de caractériser certaines classes de graphes ayant de bonnes propriétés pour la résolution de systèmes de contraintes. En effet, nous étudions ici les propriétés et algorithmes de certaines classes de graphes qui se trouvent être des généralisations des graphes triangulés. En particulier, nous étudions dans le détail les graphes CSGk, qui définissent une hiérarchie de classes de graphes dont le second niveau, les graphes CSG1 sont exactement les graphes triangulés. Dans cette étude, nous essayons de voir si les résultats classiques des graphes triangulés peuvent ou non être généralisés, en particulier aux graphes CSG2. Nous étudierons notamment le théorème de Dirac ainsi que la définition par sous-graphes exclus. Dans la dernière partie, nous étudions les aspects algorithmiques relatifs aux graphes CSG2 pour trois questions. Tout d'abord leur reconnaissance, puis le calcul des cliques maximales, et enfin, l'opération qui consiste à ajouter des arêtes dans un graphe quelconque afin de construire un graphe CSG2 ; nous nommerons cette opération "2-triangulation". Il s'agit là d'outils algorithmiques qui trouvent leur justification notamment pour la généralisation de la méthode de décomposition de domaines par triangulation. La dernière contribution de cette thèse repose sur deux généralisations de classes polynomiales du problème de la clique : les graphes faiblement triangulés et les graphes de comparabilité. Ces généralisations sont construites sur le même principe que celui des graphes CSGk, à savoir une définition en termes de hiérarchie de classes de graphes. Aussi les différentes preuves s'appuient-elles sur le même type de schéma que pour les graphes CSG2, et les résultats que nous obtenons sont très similaires à ceux produits avec les graphes CSG2 en rapport principalement avec le problème de la clique.AIX-MARSEILLE1-BU Sci.St Charles (130552104) / SudocSudocFranceF