Faculté des Sciences Ain Chock Casablanca

Accueil •  Formations  • DépartementsRechercheMessageriesLiens Utiles

THESE
Présentée à la Faculté des Sciences Aïn Chock
En vue de l’obtention du

DOCTORAT D’ETAT
Es-Sciences Matématiques

Par
Pr. Abderrahim BOUSSAÏRI

DIFFERENTS TYPES DE RECONNAISSANCE EN THEORIE DES GRAPHES

Date : le Jeudi 12 Juillet 2007 à 10 h à l’Amphi I devant le jury constitué de :
Pr. Mustapha BOUHAMZA; Faculté des Sciences Aïn Chock (Président)
Pr. Mohamed BOUCHOUM; Faculté des Sciences Aïn Chock (Directeur)
Pr. Driss MISANE; Faculté des Sciences Rabat (Rapporteur)
Pr. Jean-Xavier RAMPON; Université de Nantes (Rapporteur)
Pr. Mustapha KABIL; FST Mohammedia (Examinateur)
Pr. Aboubakr LBEKKOURI; Faculté des Sciences Rabat (Examinateur)

Résumé:
Le présent travail porte sur différents problèmes combinatoires de reconnaissance dans lesquels l'indécomposabilité joue un rôle prépondérant. En théorie des graphes, les problèmes de reconnaissance consistent à obtenir des informations globales concernant un graphe à partir d'informations locales sur une famille de ses sous-graphes.
Dans un premier temps, nous envisageons le problème de reconnaissance de l'isomorphie. Plus particulièrement, nous étudions le problème suivant : Quelles conditions doit satisfaire un graphe G pour que tous les graphes, obtenus à partir de G en inversant l'orientation de certaines paires orientées, soient isomorphes à G ? Ensuite, nous présentons différentes généralisations du résultat suivant dû à T. Gallai : Étant donné deux ordres partiels O et O' définis sur le même ensemble de V et admettant les mêmes paires de sommets comparables; Si O est indécomposable alors O=O' ou O est l'ordre inverse de O. Enfin, nous abordons le problème de la reconnaissance de l'indécomposabilité d'un graphe, en considérant la famille de ses sous-graphes de à 3 ou 4 sommets.
Mots clés:
Graphe; tournoi; reconnaissance; indécomposabilité; intervalle; dualité; hémimorphie; hypomorphie; reconstruction.

 

© 2006 Faculté des Sciences Ain Chock Casablanca Maroc