12. Structures récursives non linéaires :
les réseaux

Un réseau est un graphe orienté et pondéré, c'est-à-dire que chaque arc, en plus d'un sens, possède une valeur associée qui représente la "capacité" de liaison de l'arc. Par exemple :

               une distance, un coût, un débit maximum, etc . . .

Le problème qui consiste à déterminer quel est le flot optimum que l'on peut obtenir à travers un réseau est un problème non trivial dont l'étude détaillée est du domaine de la recherche opérationnelle.

Pour définir un problème de flot dans un réseau, on fera les hypothèses suivantes :

  1. il n'y a qu'une source (ou point de départ)
  2. il n'y a qu'une seule destination vers laquelle tous les arcs convergent;
  3. on suppose que les sommets intermédiaires sont des vannes qui, par réglages adéquats, permettent d'optimiser le flot à travers l'ensemble du réseau (flot : le long d'un arc, à travers un sommet).

De par ces hypothèses, on se limitera donc dans ce chapitre à n'aborder qu'une certaine catégorie de problèmes liés aux graphes orientés pondérés. Au nombre des utilisations de telles structures, on peut citer:

12.1. Capacité et écoulement

Table des matières.

Site Hosting: Bronco