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éfinition[modifier | modifier le code]

Soit $G=(V,E)$ un graphe orienté fini dans lequel chaque arête est associée à une valeur réelle positive $\ c(u,v)$ . Si $\ (u,v)\not \in E$ , on suppose que $\ c(u,v)=0$ . On distingue 2 sommets particuliers: une source $\ s$ et un puits $\ t$ . Un flot dans le réseau est une fonction à valeur réelle $\ f:V\times V\rightarrow \mathbb {R}$ qui, pour tous sommets $\ u$ et $\ v$ , vérifie les 3 propriétés suivantes :

Contraintes de capacité

\ f(u,v)\leq c(u,v)

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

Anti-symétrie

\ f(u,v)=-f(v,u)

. Le flot du sommet

\ u

vers le sommet

\ v

doit être l'opposé du flot de

\ v

vers

\ u

(voir l'exemple).

Conservation du flot

\ \sum _{w\in V}f(u,w)=0

, sauf si

\ u=s

ou

\ u=t

. 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 :

\ \sum _{u\in V}f(u,v)=\sum _{z\in V}f(v,z)

,

pour tout sommet $\ {v\in V\setminus \{s,t\}}$

À noter que $\ f(u,v)$ est le flot signé de $\ u$ à $\ v$ . 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 $\ u$ vers $\ v$ , et un flot réel de 3 unités de $\ v$ vers $\ u$ , on a $\ f(u,v)=1$ et $\ f(v,u)=-1$ .

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

\ \sum _{(s,v)\in E}f(s,v)

.

La capacité résiduelle d'une arête est $\ c_{f}(u,v)=c(u,v)-f(u,v)$ . On peut donc définir le réseau résiduel noté $\ G_{f}=(V,E_{f})$ , qui indique la quantité de capacité disponible. À noter qu'il peut y avoir un chemin de $\ u$ vers $\ v$ 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 $\ v$ vers $\ u$ équivaut à augmenter le flot de $\ u$ vers $\ v$ . Un chemin croissant est un chemin $\ (u_{1},u_{2},\dots ,u_{k})$ dans le réseau résiduel, où $\ u_{1}=s$ , $\ u_{k}=t$ , et $\ c_{f}(u_{i},u_{i+1})>0$ . Un réseau est à flot maximal si et seulement s'il n'existe aucun chemin dans le réseau résiduel $\ G_{f}$ .

Plus précisément, les arêtes $\ E_{f}$ de $\ G_{f}$ sont construites comme suit : pour chaque arête $\ (x,y)\in E$ :

si $\ f(x,y)<c(x,y),$ , créer une arête dans le sens positif $\ (x,y)\in E_{f}$ avec une capacité égale à $\ c_{f}=c(x,y)-f(x,y)$ .
si $\ f(x,y)>0,$ , créer une arête dans le sens négatif $\ (y,x)\in E_{f}$ avec une capacité égale à $\ c_{f}=f(x,y)$ .

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].

Exemple[modifier | modifier le code]

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

À droite est représenté un réseau de flot avec une source notée $s$ , un puits $t$ , et quatre nœuds supplémentaires. Le flot et la capacité sont notés $f/c$ . 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 $s$ vers $t$ vaut 5, ce qui peut simplement se vérifier en raison du fait que la somme de flot émanant de $s$ vaut 5, ce qui est également la quantité de flot parvenant à $t$ . De plus, on sait que pour les autres nœuds, la somme de flot entrant est égale à celle sortant.

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 $(d,c)$ . Ce flot n'est pas un flot maximal. En effet, il reste de la capacité disponible le long des chemins $(s,a,c,t)$ , $(s,a,b,d,t)$ et $(s,a,b,d,c,t)$ . La capacité résiduelle du premier chemin est égale à $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(5-3,3-2,2-1)=\min(2,1,1)=1$ . À 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 aussi[modifier | modifier le code]

Références[modifier | modifier le code]

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

Bibliographie[modifier | modifier le code]

(en) George T. Heineman, Gary Pollice et Stanley Selkow, Algorithms in a Nutshell, O'Reilly Media, 2008, 343 p. (ISBN 978-0-596-51624-6), chapitre 8 : « Network Flow Algorithms », p. 226–250
(en) Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows : Theory, Algorithms and Applications, Prentice Hall, 1993, 846 p. (ISBN 0-13-617549-X)
(en) Bollobás, Béla, Graph Theory : An Introductory Course, Heidelberg, Springer-Verlag, 1979 (ISBN 3-540-90399-2)
(en) Chartrand, Gary & Oellermann, Ortrud R., Applied and Algorithmic Graph Theory, New York, McGraw-Hill, 1993, 295 p. (ISBN 0-07-557101-3)
(en) Shimon Even, Graph Algorithms, Rockville, Maryland, Computer Science Press, 1979 (ISBN 0-914894-21-8)
(en) Alan Gibbons, Algorithmic Graph Theory, Cambridge, Cambridge University Press, 1985, 259 p. (ISBN 0-521-28881-9, lire en ligne)
(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press and McGraw-Hill, 2001, 2^e éd. (1^re éd. 1990), 1180 p. (ISBN 0-262-03293-7), chapitre 26, p. 696–697

Liens externes[modifier | modifier le code]

Maximum Flow Problem
Maximum Flow
Real graph instances
Software, papers, test graphs, etc.
Software and papers for network flow problems
Lemon C++ library with several maximum flow and minimum cost circulation algorithms
QuickGraph, graph data structures and algorithms for .Net

Portail de l'informatique théorique

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

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

[1]

[2]