Abstract FR:

Cette these porte sur l'etude de differentes structures et problemes de communication dans les reseaux d'interconnexion. La premiere partie est consacree a un nouveau reseau, la grille d'arbres d-aires, dans lequel divers algorithmes de communication sont developpes. Plusieurs plongements et multiplongements de ce reseau dans le graphe de de bruijn sont aussi presentes. Enfin, une nouvelle approche de plongement est proposee, qui tient compte de certaines proprietes concernant la nature des nuds d'une architecture, et l'execution d'un algorithme parallele dans un reseau. La seconde partie traite des largeurs de bande et de coupe d'un graphe. De nouvelles majorations sont proposees en utilisant la notion de graphe quotient d'un graphe par une partition de l'ensemble de ses sommets. Ces resultats permettent d'obtenir des encadrements serres pour de nombreux reseaux. Enfin, la troisieme partie concerne l'etude de plusieurs conjectures liees a l'existence de cycles et circuits hamiltoniens deux a deux arete-disjoints dans le graphe de de bruijn et dans le graphe butterfly