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.
Complete list of metadatas

https://hal.inria.fr/inria-00471716
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 5:52:40 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on : Friday, July 9, 2010 - 9:21:13 PM

Files

vuibert07.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

226

Files downloads

273