Sur La Représentation Des Graphes Et Des Ordres : Problèmes De Satisfaction De Contraintes

Résumé: Nous avons étudié dans cette thèse les homomorphismes de graphe et nous déduisons que la notion d'homomorphisme généralise la notion de coloration, nous étendons ces notion vers les nombres chromatique fractionnaire, nous montrons comment trouver la borne supérieure et la borne inférieure d'un nombre chromatique fractionnaire de produit de deux graphes. Nous présentons aussi quelques exemples concrets des CSP, comme le problème des n-reines et le problème de coloriage d'une carte. Nous avons étudié aussi la complexité algorithmique de problème de satisfaction de contraintes dans un domaine fini L'analyse de ces problèmes est basée sur l'algèbre universelle. Nous présentons les CSP sous forme de contraintes basées sur les ensembles finis de relations (co-clones) fermés par rapport aux ensembles de fonctions (clones) appel´es les polymorphismes. Nous abordons les CSP booléens de façon détaillée. Ensuite, nous étudions les clones, ils forment un treillis ordonné par inclusion, le treillis de Post. Nous abordons la notion de correspondance deGalois, d'abord en général, puis appliquée aux clones et co-clones. Cette dernière nous permet de caractériser totalement la complexité des CSP pour tout langage booléen de contraintes, arrivant au fameux théorème dichotomique de Schaefer classant des CSP booléens en polynomiaux et NP-complets. Nous étudions les conditions suffisantes pour la traçabilité.

Publié dans la revue: