Abstract FR:

Cette these porte sur les problemes d'emulation et de tolerance aux pannes dans les reseaux d'interconnexion. Ces derniers sont modelises par des graphes orientes (ou non), ou les sommets du graphe representent les ressources (entites materielles ou logicielles) du reseau et les arcs (ou aretes) les liens de communication entre les ressources. L'etude menee dans cette these porte principalement sur les reseaux de de bruijn et de kautz. Pour etudier l'emulation d'un grand reseau par un autre plus petit, nous avons utilise un outil theorique base sur la notion d'homomorphisme de graphe. Nous avons etudie plus particulierement les homomorphismes des graphes de de bruijn et de kautz. Les homomorphismes obtenus nous ont permis de decrire des methodes permettant d'emuler efficacement les algorithmes de type diviser pour regner ainsi que des algorithmes de reconfiguration dans ces reseaux. Deux modeles de tolerance aux pannes sont consideres dans cette these. Le premier est base sur l'ajout de ressources redondantes. En utilisant ce modele, nous avons construit des reseaux de de bruijn et de kautz dits k-tolerants. Ces reseaux ont la particularite de contenir une copie d'un reseau de de bruijn ou de kautz apres une panne de k ressources quelconques. Le second modele est celui de t-spanner. Nous avons construit, pour t = 3 ou 7, des t-spanners des graphes sous-jacents aux graphes representatifs des arcs iteres. Ces resultats generaux, nous ont permis d'en deduire des t-spanners des graphes de de bruijn, de kautz et butterfly