Réseau de flot

En théorie des graphes, un réseau de flot (aussi appelé réseau de transport) est un graphe orienté où chaque arête possède une capacité et peut recevoir un flot (ou flux). Le cumul des flots sur une arête ne peut pas excéder sa capacité. Un graphe orienté est souvent appelé réseau en recherche opérationnelle. Les sommets sont alors appelés des nœuds et les arêtes des arcs. Pour qu'un flot soit valide, il faut que la somme des flots atteignant un nœud soit égale à la somme des flots quittant ce nœud, sauf s'il s'agit d'une source (qui n'a pas de flot entrant), ou d'un puits (qui n'a pas de flot sortant). Un réseau peut être utilisé pour modéliser le trafic dans un réseau routier, la circulation de fluides dans des conduites, la distribution d'électricité dans un réseau électrique, ou toutes autres données transitant à travers un réseau de nœuds.

DéfinitionModifier

Soit   un graphe orienté fini dans lequel chaque arête est associée à une valeur réelle positive  . Si  , on suppose que  . On distingue 2 sommets particuliers: une source   et un puits  . Un flot dans le réseau est une fonction à valeur réelle   qui, pour tous sommets   et  , vérifie les 3 propriétés suivantes:

Contraintes de capacité

 . Le flot sur une arête ne peut excéder sa capacité.

Anti-symétrie

 . Le flot du sommet   vers le sommet   doit être l'opposé du flot de   vers   (voir l'exemple).

Conservation du flot

 , sauf si   ou  . Le cumul signé des flots entrant et sortant d'un nœud est nul, sauf pour la source qui en produit, ou pour le puits, qui en consomme.

Dit autrement, la conservation du flot entraîne :

 ,

pour tout sommet  

À noter que   est le flot signé de   à  . Si le graphe représente un réseau physique, et s'il s'agit d'un flot réel de, par exemple, 4 unités de   vers  , et un flot réel de 3 unités de   vers  , on a   et  .

On dit que le flot (au sens général) d'un réseau physique est le flot partant de la source s, soit

 .

La capacité résiduelle d'une arête est  . On peut donc définir le réseau résiduel noté  , qui indique la quantité de capacité disponible. À noter qu'il peut y avoir un chemin de   vers   dans le réseau résiduel, même si ce chemin n'existe pas dans le réseau original. Puisque 2 flots de directions opposées s'annulent, faire décroître le flot de   vers   équivaut à augmenter le flot de   vers  . Un chemin croissant est un chemin   dans le réseau résiduel, où  ,  , et  . Un réseau est à flot maximal si et seulement s'il n'existe aucun chemin dans le réseau résiduel   .

Plus précisément, les arêtes  de   sont construites comme suit : pour chaque arête   :

  • si   , créer une arête dans le sens positif   avec une capacité égale à  .
  • si  , créer une arête dans le sens négatif   avec une capacité égale à  .

Ce type de construction est utilisé notamment dans l'algorithme de Ford-Fulkerson qui calcule un flot maximal dans un réseau de flot.

Parfois, il est nécessaire de modéliser un réseau avec plus d'une source. Une supersource est alors introduite dans le graphe[1]. Elle consiste en un sommet connecté à chaque source, avec des arêtes de capacité infinie, de manière à se comporter comme une source unique et globale. Une construction similaire pour les puits est appelée superpuits[2].

ExempleModifier

 
Un réseau de flot illustrant la notion de capacité

À droite est représenté un réseau de flot avec une source notée  , un puits  , et quatre nœuds supplémentaires. Le flot et la capacité sont notés  . On peut noter que le réseau est anti-symétrique, en raison des contraintes de capacité et de conservation du flot. La somme totale de flot depuis   vers   vaut 5, ce qui peut simplement se vérifier en raison du fait que la somme de flot émanant de   vaut 5, ce qui est également la quantité de flot parvenant à  . De plus, on sait que pour les autres nœuds, la somme de flot entrant est égale à celle sortant.

 
Réseau résiduel du réseau ci-dessus, représentant les capacités résiduelles.

Sur le schéma ci-contre est représenté le réseau résiduel. On note qu'on peut trouver une capacité positive sur certaines arêtes où la capacité d'origine est nulle, par exemple l'arête  . Ce flot n'est pas un flot maximal. En effet, il reste de la capacité disponible le long des chemins  ,   et  . La capacité résiduelle du premier chemin est égale à    . À noter que tant qu'il existe un chemin avec une capacité résiduelle positive, le flot ne peut être maximal. La capacité résiduelle d'un chemin est le minimum des capacités résiduelles des arêtes qui composent le chemin.

Voir aussiModifier

RéférencesModifier

  1. (en) Paul E. Black, « Supersource », Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.
  2. (en) Paul E. Black, « Supersink », Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.

BibliographieModifier

Liens externesModifier