Abstract FR:

De nos jours, les reseaux jouent un role de plus en plus important. On les retrouve dans la telephonie mobile (reseaux terrestres ou constellation de satellites), dans l'internet, dans les machines paralleles (reseaux de processeurs), etc. Chaque unite composant ces reseaux possede une certaine information, et, en cours d'utilisation, ces informations doivent etre communiquees : principalement, ces communications sont la diffusion (ou one-to-all), l'echange total (ou all-to-all), et le multicast (ou one-to-many). L'objet de cette these est d'etudier la diffusion et l'echange total dans ces reseaux. Plus precisement, nous passons en revue un certain nombre de modeles (full-duplex, simplex, temps constant, temps lineaire, etc. ), et, pour chacun d'entre eux, nous realisons une etude sur deux aspects fondamentaux mesurant l'efficacite des ces reseaux : le temps de communication dans un reseau compose de n unites et entierement connecte ; et le nombre minimum de liens effectivement utilises par le reseau pour communiquer en temps minimum. Dans certains modeles ou le temps de communication n'est pas connu precisement, nous ameliorons cette connaissance (echange total simplex), ou determinons avec exactitude ce temps (echange total full-duplex temps lineaire). Dans l'echange total full-duplex temps lineaire, nous etudions egalement les compromis possibles entre nombre d'etapes et nombre de pas. Nous determinons avec exactitude le nombre minimum de liens dans un reseau a n entites pour certaines valeurs infinies de n (diffusion simplex pour tout n = 2#k 1 et n = 2#k 2). De plus, nous presentons une methode efficace de composition de graphes permettant d'obtenir des bornes superieures sur le nombre minimum de liens (echange total full-duplex temps constant et temps lineaire). Enfin, nous obtenons divers resultats exacts pour quelques valeurs particulieres de n. Dans un deuxieme temps, nous exhibons une famille de graphes possedant de bonnes proprietes en terme de diffusion et d'echange total, dans quasiment tous les modeles etudies. Ces graphes sont appeles graphes de knodel, et sont etudies extensivement dans ce memoire.