Flots dans les réseaux

Youssou Dieng

Universités: Ziguinchor

(Cours RO: L3 Informatique)

Avril 2012
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Introduction

Un système dans lequel un matériau s’écoule, tel l’eau ou

l’électricité, peut être modélisé à l’aide dun graphe.
Une question naturelle se pose: quelle est la capacité
maximale de ce système?
Ce problème est connu sous le nom de flot maximal et
admet plusieurs solutions algorithmiques efficaces. [Nous
en présenterons ici quelques unes.]
Les graphes concidérés ici, sont sauf mention contraire,
simples et orientés
Introduction

Définition
Un flot dans un graphe G = (X, U ) est un vecteur
φ = {φ1 , φ2 , . . . , φm } ∈ Rm tel que:
La quantité de flot ou flux sur l’arc j, est φj pour
j = 1, 2, . . . , m.
Pour tout sommet x ∈ X, la 1iere loi de Kirchhoff est
vérifiée.
P P
j∈ω + (i) φj = j∈ω − (i) φj .
Flot dans les réseaux de transport

Un réseau de transport est un graphe orienté connexe

G = (X, U ) avec:
un sommet s sans prédecesseur appelé entrée ou sorce
(γ − (s) = ∅).
un sommet t sans suivant appelé sortie ou puit
(γ + (s) = ∅).
Caractéristiques

Contrainte de capacité: Pour tout arc (u, v) ∈ U , on a:

f (u, v) 6 c(u, v).
Symétrie: Pour tout arc (u, v) ∈ E, on a:
f (u, v) = −f (v, u).
Concervation du flot : tout sommet u ∈ V {s, t} vérifie:
P
v∈V f (u, v) = 0.
La valeur du flot f , notée |f | est la quantité
P
v∈V f (s, v).

Le problème du flot maximal consiste à calculer pour tout

réseau un flot de valeur maximale.
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Réseau résiduel
Tout flot de valeur non nulle est si il n’est pas maximal un
début de réponse.
En effet, on peut définir à partir de ce réseau G un
nouveau réseau G′ “plus simple” pour lequel tout flot
maximal f ′ permettra de définir le flot maximal f ′ + f sur
G.
Réseau résiduel
Tout flot de valeur non nulle est si il n’est pas maximal un
début de réponse.
En effet, on peut définir à partir de ce réseau G un
nouveau réseau G′ “plus simple” pour lequel tout flot
maximal f ′ permettra de définir le flot maximal f ′ + f sur
G.

Définition
La capacité résiduelle d’un réseau (V, U, c, s, t) induit par un
flot f est la fonction notée cf qui associe à tout arc
(u, v) ∈ E le réel positif ou nul c(u, v) − f (u, v). Le réseau
résiduel dun réseau (V, U, c, s, t) induit par un flot f est le
réseau (V, U, cf , s, t).
Réseau résiduel
Lemme
Si f est un flot sur un réseau G et
Si g est un flot sur le réseau résiduel de G induit par f ,
Alors f + g est un flot de G de valeur |f + g| = |f | + |g|.
Réseau résiduel
Lemme
Si f est un flot sur un réseau G et
Si g est un flot sur le réseau résiduel de G induit par f ,
Alors f + g est un flot de G de valeur |f + g| = |f | + |g|.

Proof.
Soit f un flot sur un réseau G = (V, E, c, s, t) et g un flot
sur le réseau résiduel de G induit par f .
Démontrons que la foncton h := f + g est un flot de G
de valeur |f | + |g|:
1. h vérifie la containte de capacité: Par définition, pour
tout arc e de E: cf (e) = c(e) − f (e) et g(e) 6 cf (e) et
donc h(e) = f (e) + g(e) 6 f (e) + (c(e) − f (e)) 6 c(e).
2. h vérifie la symétrie: la somme de deux fonctions
symétriques est clairement symétrique.
Réseau résiduel

3. h conserve le flot: Soit un sommet

P u autre que la source
et le puits de G. P
P La quantité v∈V h(u, v) est égale à
v∈V f (u, v) + v ∈ V g(u, v) = 0 + 0 = 0.
4. LaP |f | + |g|: Par définition, |h| est égale
valeur de h est P
à v∈V f (s, v) + v∈V g(s, v) = |f | + |g|.
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Chemin améliorant
Définir un flot peut se faire en choisissant simplement dans le
réseau un chemin de s à t et en prenant pour valeur la capacité
minimale des arcs de ce chemin.
Chemin améliorant
Définir un flot peut se faire en choisissant simplement dans le
réseau un chemin de s à t et en prenant pour valeur la capacité
minimale des arcs de ce chemin.
Définition
Soit G = (V, U, c, s, t) un réseau et p un chemin élémentaire dans
G de s à t. La capacité de p est le minimum des capacités des arcs
que possède p et est noté c(p). Le flot induit par p est la fonction
notée fp qui associe à tout arc (u, v) ∈ V 2 la quantité définie par:

c(p) si (u, v) appartient à p.

−c(p) si (v, u) appartient à p.

0 sinon.
Chemin améliorant
Un chemin p allant de s à t améliore (ou est un chemin
augmentant) un flot f de G si la capacité de p dans le réseau
résiduel de G induit par f est > 0.
Un chemin améliorant, est un chemin du réseau résiduel,
allant de s à p et sans circuit.
Chemin améliorant
Un chemin p allant de s à t améliore (ou est un chemin
augmentant) un flot f de G si la capacité de p dans le réseau
résiduel de G induit par f est > 0.
Un chemin améliorant, est un chemin du réseau résiduel,
allant de s à p et sans circuit.

Lemme
La fonction fp induit par un chemin élémentaire p de la source au
puits dans un réseaux est un flot de valeur c(p).
Chemin améliorant
Un chemin p allant de s à t améliore (ou est un chemin
augmentant) un flot f de G si la capacité de p dans le réseau
résiduel de G induit par f est > 0.
Un chemin améliorant, est un chemin du réseau résiduel,
allant de s à p et sans circuit.

Lemme
La fonction fp induit par un chemin élémentaire p de la source au
puits dans un réseaux est un flot de valeur c(p).

Proof.
1. fp vérifie la contrainte de capacité. Trivialement le flot de
tout arc est inférieur à sa capacité.

2. fp vérifie la symétrie. (Une conséquence triviale de la

définition)
Chemin améliorant

3. fp conserve le flot. Soit u un sommet de V {s, t}.

3.1 Si u n’appartient pas à p, tout arc incident à u a un flot

nul. [La somme de ces flots est donc nulle.]
3.2 Sinon, u est nécessairement un sommet interne de p.
[∃ deux arcs de la forme (x, u) et (u, y) appartenant à p.]

4 La valeur de fp est c(p). L’unique arc de p incident à s est de

la forme (s, u) avec u ∈ V . Ainsi, |fp | = fp (s, u) = c(p).
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
MaxiFlot & MiniCoupe
Une coupe dans un réseau G = (V, U, c, s, t) est un couple
d’ensemble de sommets de forme (X, Y = V − X) avec
X ⊆ V tel que s ∈ X et t ∈ Y .
P
Sa capacité, noté c(X, Y ) est la somme x∈X,y∈Y c(x, y).
Une coupe est minimale si sa capacité est au plus égale à la
capacité de toute coupe de ce réseau.
Le flot d’une coupe (X, Y ) relativement à un flot f est la
quantité f (X, Y ).
MaxiFlot & MiniCoupe
Une coupe dans un réseau G = (V, U, c, s, t) est un couple
d’ensemble de sommets de forme (X, Y = V − X) avec
X ⊆ V tel que s ∈ X et t ∈ Y .
P
Sa capacité, noté c(X, Y ) est la somme x∈X,y∈Y c(x, y).
Une coupe est minimale si sa capacité est au plus égale à la
capacité de toute coupe de ce réseau.
Le flot d’une coupe (X, Y ) relativement à un flot f est la
quantité f (X, Y ).

Lemme
Tout flot f et toute coupe (X, Y ) d’un même réseau de capacité c
vérifient: |f | = f (X, Y ) 6 c(X, Y ).
MaxiFlot & MiniCoupe
Une coupe dans un réseau G = (V, U, c, s, t) est un couple
d’ensemble de sommets de forme (X, Y = V − X) avec
X ⊆ V tel que s ∈ X et t ∈ Y .
P
Sa capacité, noté c(X, Y ) est la somme x∈X,y∈Y c(x, y).
Une coupe est minimale si sa capacité est au plus égale à la
capacité de toute coupe de ce réseau.
Le flot d’une coupe (X, Y ) relativement à un flot f est la
quantité f (X, Y ).

Lemme
Tout flot f et toute coupe (X, Y ) d’un même réseau de capacité c
vérifient: |f | = f (X, Y ) 6 c(X, Y ).

Proof.
Soit f un flot, (X, V − X) une coupe dans un réseau
MaxiFlot & MiniCoupe
G = (V, E, c, s, t). L’inégalité f (X, Y ) 6 c(X, Y ) est une
conséquence de l’inégalité f (e) 6 c(e) vérifiée par toute arc e.
...
MaxiFlot & MiniCoupe
G = (V, E, c, s, t). L’inégalité f (X, Y ) 6 c(X, Y ) est une
conséquence de l’inégalité f (e) 6 c(e) vérifiée par toute arc e.
...

Théorème
Soit f un flot dans un réseau G. Les quatre assertions suivantes
sont équivalentes:

1. f est un flot maximal.

2. f n’admet aucun chemin améliorant.

3. Il existe une coupe dans le réseau résiduel induit par f de

capacité nulle.

4. Il existe une coupe (X, Y ) de capacité cG (X, Y ) égale au flot

f (X, Y ).
MaxiFlot & MiniCoupe
Proof.
Soit G = (V, E, c, s, t) un réseau, f un flot et H le réseau résiduel
de G et f . il vient:
MaxiFlot & MiniCoupe
Proof.
Soit G = (V, E, c, s, t) un réseau, f un flot et H le réseau résiduel
de G et f . il vient:
4 ⇔ 3 Conséquence immédiate de la définition du réseau résiduel
de G, H induit par f , pour toute coupe (X, Y ) de G et donc de
H, on a : cH (X, Y ) = cG (X, Y )f (X, Y ). Ce qui suffit à conclure
MaxiFlot & MiniCoupe
Proof.
Soit G = (V, E, c, s, t) un réseau, f un flot et H le réseau résiduel
de G et f . il vient:
4 ⇔ 3 Conséquence immédiate de la définition du réseau résiduel
de G, H induit par f , pour toute coupe (X, Y ) de G et donc de
H, on a : cH (X, Y ) = cG (X, Y )f (X, Y ). Ce qui suffit à conclure
3 ⇒ 1 Du simple fait que tout arc (u, v) a un flot f (u, v) au plus
égal à sa capacité c(u, v). On en déduit que toute coupe a un flot
au plus égal à sa capacité.
MaxiFlot & MiniCoupe
Proof.
Soit G = (V, E, c, s, t) un réseau, f un flot et H le réseau résiduel
de G et f . il vient:
4 ⇔ 3 Conséquence immédiate de la définition du réseau résiduel
de G, H induit par f , pour toute coupe (X, Y ) de G et donc de
H, on a : cH (X, Y ) = cG (X, Y )f (X, Y ). Ce qui suffit à conclure
3 ⇒ 1 Du simple fait que tout arc (u, v) a un flot f (u, v) au plus
égal à sa capacité c(u, v). On en déduit que toute coupe a un flot
au plus égal à sa capacité.
Or tout flot a une valeur égale au flot d’une quelconque coupe
[Lemme3]. Ainsi la valeur de tout flot est au plus égale à la
capacité d’une quelconque coupe. En d’autre termes, si un flot f
et une coupe (X, Y ) sont tels que |f | = c(X, Y ), alors f est un
flot maximal.
MaxiFlot & MiniCoupe
Proof.
Soit G = (V, E, c, s, t) un réseau, f un flot et H le réseau résiduel
de G et f . il vient:
4 ⇔ 3 Conséquence immédiate de la définition du réseau résiduel
de G, H induit par f , pour toute coupe (X, Y ) de G et donc de
H, on a : cH (X, Y ) = cG (X, Y )f (X, Y ). Ce qui suffit à conclure
3 ⇒ 1 Du simple fait que tout arc (u, v) a un flot f (u, v) au plus
égal à sa capacité c(u, v). On en déduit que toute coupe a un flot
au plus égal à sa capacité.
Or tout flot a une valeur égale au flot d’une quelconque coupe
[Lemme3]. Ainsi la valeur de tout flot est au plus égale à la
capacité d’une quelconque coupe. En d’autre termes, si un flot f
et une coupe (X, Y ) sont tels que |f | = c(X, Y ), alors f est un
flot maximal.
1 ⇒ 2 Si p est un chemin améliorant du flot f , le Lemme2 indique
que le flot fp est de valeur strictement positive. Le Lemme 1
indique que f + fp est un flot de G de valeur |f | + |f p| > |f |
MaxiFlot & MiniCoupe

et donc que f n’est pas maximal. Ainsi, si f est maximal, il n’est

amélioré par aucun chemin.
MaxiFlot & MiniCoupe

et donc que f n’est pas maximal. Ainsi, si f est maximal, il n’est

amélioré par aucun chemin.
2 ⇒ 3 Supposons que f n’admet aucun chemin améliorant. Soit X
l’ensemble des sommets accessibles à partir de s en utilisant des
chemins à arc de capacité résiduel cH (u, v) > 0.
MaxiFlot & MiniCoupe

et donc que f n’est pas maximal. Ainsi, si f est maximal, il n’est

amélioré par aucun chemin.
2 ⇒ 3 Supposons que f n’admet aucun chemin améliorant. Soit X
l’ensemble des sommets accessibles à partir de s en utilisant des
chemins à arc de capacité résiduel cH (u, v) > 0. Conséquence de
la définition de chemin améliorant est que t n’appartient pas à
X...De plus tout arc (x, y) ∈ X × V − X est de capacité résiduelle
nulle c’est- à-dire vérifié f (x, y) = cH (x, y) ainsi la coupe (X, Y ) a
une capacité nulle dans H (cH (X, Y ) = 0)............
MaxiFlot & MiniCoupe

et donc que f n’est pas maximal. Ainsi, si f est maximal, il n’est

amélioré par aucun chemin.
2 ⇒ 3 Supposons que f n’admet aucun chemin améliorant. Soit X
l’ensemble des sommets accessibles à partir de s en utilisant des
chemins à arc de capacité résiduel cH (u, v) > 0. Conséquence de
la définition de chemin améliorant est que t n’appartient pas à
X...De plus tout arc (x, y) ∈ X × V − X est de capacité résiduelle
nulle c’est- à-dire vérifié f (x, y) = cH (x, y) ainsi la coupe (X, Y ) a
une capacité nulle dans H (cH (X, Y ) = 0)............

Corollaire
Pour tout réseau, la valeur maximale des flots est égale à la
capacité minimale des coupes.
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Une solution au problème du flot maximal

1. Intitulé du problème: Flot maximum

2. Description des paramètres: Un graphe orienté G = (S, A)

où chaque arête est valuée par sa capacité, un sommet source
et un sommet puits.

3. Question: Quel est la flot maximum qu’il est possible de

faire passer dans ce réseau depuis la source vers le puits?
Une solution au problème du flot maximal

Algorithme de FordFulkerson
Fonction FordFulkerson (G = (V, U, c, s, t): réseau): flot;
f max ← 0;
tantque il existe un chemin de s à t de capacité > 0
faire
calculer un chemin p élémentaire de s à t de capacité
> 0;
f ← flotInduit(G, p);
G ← réseauRésiduel(G, f );
f max ← f max + f ;
retouner f max;
Outline

Introduction

Réseau résiduel

Chemin améliorant

MaxiFlot & MiniCoupe

Une solution au problème du flot maximal

Références bibliographiques
Références bibliographiques
P. Lopez, Cours de graphes, LAAS-CNRS
[Link]
Ph. Vallin and D. Vanderpooten. Aide la dcision : une
approche par les cas. Ellipses, Paris, 2000.
M. Gondron, M. Minoux, Graphes et algorithmes,
Eyrolles, Paris, 1984
C. Prins, Algorithmes de graphes, Eyrolles, Paris, 1994
Ph. Lacomme, C. Prins, M. Sevaux, Algorithmes de
graphes, Eyrolles, 2003
B. Baynat, Ph. Chrtienne, ..., Exercices et problmes
dalgorithmique, Dunod, 2003
E. Lawler, Combinatorial Optimization Networks and
matroids, Dover Publications, INC, 1976.