Utilisateur:HeyCat/Brouillon2

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 flot atteignant un nœud soit égale à la somme des flots quittant ce nœud, soit 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 toute autres données transitant à travers un réseau de nœud.

Définition

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 unz fonction à valeur réelle $\ f:V\times V\rightarrow \mathbb {R}$ qui, pour tout sommet $\ u$ and $\ 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 noeud 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,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)$, pour tout sommet $\ {v\in V\setminus \{s,t\}}$

A 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 emmenant de la source s = $\ \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. A 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 si il n'existe aucun chemin dans le réseau résiduel $\ G_{f}$ .

Donc $\ G_{f}$ est construit à partir du graphe G de la façon suivante:

1. Les sommets de math>\ G_f</math> = $\ V$

2. Les arêtes de math>\ G_f</math> = $\ E_{f}$ sont définies par

Pour chaque arête math>\ (x,y) \in E </math>

    (i). Si $\ f(x,y)<c(x,y),$ , créer une arête dans le sens dans le sens positif $\ (x,y)\in E_{f}$ avec une capacité égale à $\ c_{f}=c(x,y)-f(x,y)$.
    (ii). 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é notament 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. 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 superpuit.

Exemple

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

A droite est représenté un réseau de flot avec une source notée $s$, un puit $t$, et quatre noeuds 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 les 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 noeuds, 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 $(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$. A 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é résiduelles des arêtes qui composent le chemin.

Voir aussi

• Centralité
• Théorie constructale
• Algorithme de Ford-Fulkerson
• Algorithme de Dinic
• Flux de paquets (réseau informatique)
• Théorème flot-max/coupe-min
• Matroïde orienté
• Problèmes de cheminement

Lectures complémentaires

• (en) George T. Heineman, Gary Pollice, and Stanley Selkow, Algorithms in a Nutshell, Oreilly Media, 2008, 226–250 p. (ISBN 978-0-596-51624-6), « Chapter 8:Network Flow Algorithms »
• (en) Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993 (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 (ISBN 0-07-557101-3)
• (en) Even, Shimon, Graph Algorithms, Rockville, Maryland, Computer Science Press, 1979 (ISBN 0-914894-21-8)
• (en) Gibbons, Alan, Algorithmic Graph Theory, Cambridge, Cambridge University Press, 1985 (ISBN 0-521-28881-9)
• (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 2nd, 2001 (1^re éd. 1990), 696–697 p. (ISBN 0-262-03293-7), « 26 »

Liens externes

• 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