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.
Type de document :
Chapitre d'ouvrage
Jacky Akoka, Isabelle Comyn-Wattiau. Encyclopédie de l'informatique et des systèmes d'information, Vuibert, pp.936-945, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00471716
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 17:52:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:21:13

Fichiers

vuibert07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00471716, version 1

Collections

Citation

Laurent Viennot. Algorithmes des graphes et des réseaux. Jacky Akoka, Isabelle Comyn-Wattiau. Encyclopédie de l'informatique et des systèmes d'information, Vuibert, pp.936-945, 2006. 〈inria-00471716〉

Partager

Métriques

Consultations de la notice

195

Téléchargements de fichiers

250