Algorithmes des graphes et des réseaux
Résumé
Les graphes constituent une structure mathématique privilégiée pour modéliser les réseaux. Une grande partie de l'algorithmique des réseaux entretient donc des liens étroits avec l'algorithmique des graphes. Ce chapitre propose de mettre en lumière ces relations en explorant notamment les techniques utilisées pour coordonner entre eux les routeurs d'un réseau. La dision d'un message s'apparente ainsi au parcours d'un graphe, le problème du routage revient à calculer de plus courts chemins. Les tracs d'un réseaux se modélisent par des flots dans un graphe et les problèmes d'allocation de fréquences dans un réseau radio s'apparentent à la coloration d'un graphe. Chaque algorithme de graphe repose souvent sur l'utilisation d'une structure mathématique sous-jacente comme un chemin, un arbre ou un flot. La compréhension de l'algorithme se fonde alors sur les propriétés mathématiques de cette structure.
Origine : Fichiers produits par l'(les) auteur(s)