Algorithmes des graphes et des réseaux - Archive ouverte HAL Access content directly
Book Sections Year : 2006

Algorithmes des graphes et des réseaux

(1)
1
Laurent Viennot

Abstract

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.
Fichier principal
Vignette du fichier
vuibert07.pdf (257.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00471716 , version 1 (08-04-2010)

Identifiers

  • HAL Id : inria-00471716 , version 1

Cite

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⟩

Collections

INRIA INRIA2
132 View
184 Download

Share

Gmail Facebook Twitter LinkedIn More