Mémoires de Fin d’Etudes
Etablissement
Université d’Oran1 - Ahmed Ben Bella
Affiliation
Département de Mathématique
Auteur
TADJ, Zohra
Directeur de thèse
SI KADDOUR Hamza (Maitre de conférence)
Co-directeur
SMAIL Abderrahmene (Maitre de conférence)
Filière
Mathématiques
Diplôme
Magister
Titre
Sur la représentation des graphes et des ordres : Problèmes de satisfaction de contraintes
Mots clés
Homomorphisme de graphe; Colorabilité; Nombre chromatique fractionnaire; Programmation par contraintes; La complexité algorithmique des CSP; Problème P; Problème NP; Opérations fermés par des relations.
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és 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 de Galois, 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é.
Date de soutenance
2011
Cote
TH3472
Pagination
VI-85F.
Format
30 cm
Notes
BIBLIOG.81-83F.INDEX.
Statut
Soutenue