Nous nous intéressons à des protocoles de communications globales portant sur les graphes connexes. Dans une première partie, nous considérons le cas de l'échange total. Le Temps Minimum d'Echange Total (T.M.E.T.) est le nombre minimum d'étapes nécessaires pour que tous les sommets reçoivent tous les messages. Nous établissons des nouvelles bornes (inférieures et supérieures) sur le T.M.E.T. Nous déterminons le T.M.E.T des arbres et plus généralement des graphes de degré minimum un. Nous démontrons une conjecture de Bermond, Kodate, Marlin et Perennes sur les points fixes d'une rotation complète de certaines grilles toriques, ce qui permet de déduire l'optimalité de leur T.M.E.T. Nous montrons aussi que le T.M.E.T d'un graphe orienté de de Bruijn est optimal. Dans une seconde partie, nous considérons la problème classique de la diffusion. Nous déterminons une nouvelle borne supérieure sur le temps de diffusion d'in graphe non orienté en fonction de sa connectivité. Nous caractérisons certains graphes dont le numéro de couplage est égal au degré minimum et déterminons leur temps de diffusion. Nous donnons des résultats nouveaux sur la diffusion dans les graphes de de Bruijn. Dans la dernière partie, nous donnons des résultats originaux sur le nombre de stabilité d'un graphe de de Bruijn et plus généralement des graphes représentatifs des arcs. Nous montrons ensuite que la taille minimum d'un graphe de de Bruijn UB est ce qui valide une première conjecture de Bond. Enfin, nous prouvons que le rayon d'un graphe de Kautz est D, ce qui valide une seconde conjecture de Bond. ( d ,D ) d 1, - 2 UK( ,D )
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00214261 |
| Date | 15 December 2003 |
| Creators | Lichiardopol, Nicolas |
| Publisher | Université de Nice Sophia-Antipolis |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0012 seconds