Graphes et RO – TELECOM Nancy 2A

Chapitre 5 : Flot maximal dans un graphe

J.-F. Scheid

v2.1

1
Plan du chapitre

I. Définitions
1 Graphe
2 Graphe valué
3 Représentation d’un graphe (matrice d’incidence, matrice d’adjacence,
successeurs/prédécesseurs)
4 Flot dans un graphe
II. Problème de flot maximal dans un graphe
III. Algorithme de Ford-Fulkerson
IV. Flot maximal avec bornes inférieures et supérieures

2
1) Graphe

Graphe G = (E , Γ)
E : ensemble fini des sommets
Γ : ensemble fini de couples ordonnés (i, j) avec i, j ∈ E .
Les éléments de Γ sont appelés les arêtes du graphe

Notation :
i j

Remarque : Les graphes considérés sont tous orientés : les arêtes (i, j) et
(j, i) sont distinctes.

3
Exemple de graphe : E = {1, 2, 3, 4}
Γ = {(1, 2), (3, 4), (4, 2), (4, 3)}

1 4

4
Exemples de modélisation par des graphes :

réseau routier : les sommets sont les intersections des routes, les arêtes
représentent les routes.
cheminement dans un réseau informatique.
Web modélisé par un graphe. Les sommets sont les pages Web et les
arêtes sont les liens hypertexte entre ces différentes pages.

5
2) Graphe valué

G = (E , Γ, c) est un graphe valué si (E , Γ) est un graphe auquel on

associe une fonction positive c : Γ → R+ appelée capacité.
La capacité de l’arête (i, j) est notée cij .

Notation :
i cij j

Exemple : La capacité cij représente par exemple la longueur du tronçon de

route (i, j), le nombre max. de voitures par unité de temps entre deux villes
i et j, la bande passante maximale entre les serveurs i et j...

6
3) Représentation d’un graphe

a) Matrice d’incidence sommet-arête

Soit un graphe sans boucle c-à-d sans arête (i, i), avec n sommets et m
arêtes. On définit A la matrice d’incidence de taille n × m :

 +1 si le sommet i est l’extrémité initiale de l’arête k
aik = −1 si le sommet i est l’extrémité terminale de l’arête k
0 sinon


(k)
i j
aik = +1
ajk = −1

7
Exemple : E = {1, 2, 3, 4}
Γ = {(1, 2), (2, 3), (3, 1), (2, 4)}

(3)
1 3

(1) (2)
2 4
(4)
(1,2) (2,3) (3,1) (2,4)
1 +1 0 -1 0
Matrice d’incidence A = 2 -1 +1 0 +1
3 0 -1 +1 0
4 0 0 0 -1

8
b) Matrice d’adjacence sommet-sommet
Matrice booléenne A de taille n × n (n sommets)

1 si l’arête (i, j) existe dans le graphe
aij =
0 sinon

Variante pour un graphe valué par {cij } :


cij si l’arête (i, j) existe dans le graphe
aij =
0 sinon

9
Exemple : E = {1, 2, 3, 4}
Γ = {(1, 2), (2, 3), (3, 1), (2, 4)}

1 3

2 4

1 2 3 4
1 0 1 0 0
Matrice d’adjacence A = 2 0 0 1 1
3 1 0 0 0
4 0 0 0 0

10
c) Listes d’adjacence : successeurs et prédécesseurs

Pour chaque sommet i du graphe, on définit

la liste de ses successeurs S(i) : liste des sommets j tq l’arête (i, j)
existe dans le graphe.
la liste de ses prédécesseurs P(i) : liste des sommets j tq l’arête (j, i)
existe dans le graphe.

11
c) Listes d’adjacence : successeurs et prédécesseurs

Pour chaque sommet i du graphe, on définit

la liste de ses successeurs S(i) : liste des sommets j tq l’arête (i, j)
existe dans le graphe.
la liste de ses prédécesseurs P(i) : liste des sommets j tq l’arête (j, i)
existe dans le graphe.

Un sommet sans prédécesseur est appelé une source.

Un sommet sans successeur est appelé un puits

11
Exemple : E = {1, 2, 3, 4}
Γ = {(1, 2), (2, 3), (3, 1), (2, 4)}

1 3

2 4

sommet successeur S prédécesseur P

1 2 3
2 3, 4 1
3 1 2
4 – 2

12
4) Flot dans un graphe

Problèmes de circulation d’objets (voiture, information ...) dans un réseau

(routier, informatique ...).

Définition
Soit G = (E , Γ, c) un graphe valué comportant un seul sommet source s et
un seul sommet puits t.
Un flot de s à t est une fonction f : Γ → R tq
def
X X
fij = fjk où fij = f (i, j)
i∈P(j) k∈S(j)

pour tout sommet j 6= s, t. On dit qu’il y a conservation du flux au

sommet j ("ce qui rentre égale ce qui sort").
def
La valeur fij = f (i, j) est le flot dans l’arête (i, j).

13
Définition (suite)
Le flot est dit réalisable si pour toute arête (i, j) ∈ Γ, on a

0 ≤ fij ≤ cij
X
La quantité v = fit est la valeur du flot de s à t.
i∈P(t)

2 1
flot fij
cij 5 j 4
i j
3 5

flot entrant flot sortant

( Σ =10 ) ( Σ =10 )

14
Remarque (rappels) :

S(i) : ensemble des sommets j successeurs du sommet i c-à-d tq

l’arête (i, j) existe dans le graphe.

P(i) : ensemble des sommets j prédécesseurs du sommet i c-à-d tq

l’arête (j, i) existe dans le graphe.

Une source s (resp. un puits t ) est un sommet ne possédant pas de

prédécesseur (resp. de successeur).

s t

15
II. Problème de flot maximal dans un graphe
1) Introduction
On veut par ex. trouver le trafic maximal entre deux villes d’un réseau
routier dont on connait la capacité (nb de voiture par heure sur chaque
tronçon)
a 2 c
10 6
s 4 3
t max v ?
3 4
b 5 d

16
II. Problème de flot maximal dans un graphe
1) Introduction
On veut par ex. trouver le trafic maximal entre deux villes d’un réseau
routier dont on connait la capacité (nb de voiture par heure sur chaque
tronçon)
a 2 c
10 6
s 4 3
t max v ?
3 4
b 5 d

Problème de flot maximal

Etant donné un graphe valué possédant une seule source et un seul puits ,
trouver un flot réalisable maximal (i.e. dont la valeur est maximale).
16
Flot maximal et programmation linéaire

max [F = v ]
fij ,v

17
Flot maximal et programmation linéaire

max [F = v ]
fij ,v
 X

 fsk − v = 0 (source s)

k∈S(s)




conservation des flux
 X X
− fij + fjk = 0, ∀j 6= s, t

en chaque sommet :  i∈P(j) k∈S(j)


 X
− fit + v = 0 (puits t)





i∈P(t)

17
Flot maximal et programmation linéaire

max [F = v ]
fij ,v
 X

 fsk − v = 0 (source s)

k∈S(s)




conservation des flux
 X X
− fij + fjk = 0, ∀j 6= s, t

en chaque sommet :  i∈P(j) k∈S(j)


 X
− fit + v = 0 (puits t)





i∈P(t)

respect des capacités : fij ≤ cij pour toute arête (i, j) ∈ Γ

17
Flot maximal et programmation linéaire

max [F = v ]
fij ,v
 X

 fsk − v = 0 (source s)

k∈S(s)




conservation des flux
 X X
− fij + fjk = 0, ∀j 6= s, t

en chaque sommet :  i∈P(j) k∈S(j)


 X
− fit + v = 0 (puits t)





i∈P(t)

respect des capacités : fij ≤ cij pour toute arête (i, j) ∈ Γ

contrainte de signe : fij ≥ 0 pour toute arête (i, j) ∈ Γ

Remarque : les inconnues sont les fij et la valeur v du flot.

17
Flot maximal et programmation linéaire

max [F = v ]
fij ,v
 X

 fsk − v = 0 (source s)

k∈S(s)




conservation des flux
 X X
− fij + fjk = 0, ∀j 6= s, t

en chaque sommet :  i∈P(j) k∈S(j)


 X
− fit + v = 0 (puits t)





i∈P(t)

respect des capacités : fij ≤ cij pour toute arête (i, j) ∈ Γ

contrainte de signe : fij ≥ 0 pour toute arête (i, j) ∈ Γ

Remarque : les inconnues sont les fij et la valeur v du flot.

17
Flot maximal et programmation linéaire
Ecriture matricielle (n sommets et m arêtes)

max [F = v ]
f,v

 Af + v = 0
f≤c
f≥0


A est la matrice d’incidence du graphe, de taille n × m,

 
(fsk )k∈S(s)  
−v
..
 0 
 
.
   
.
 ∈ Rm ; v =  ..  ∈ Rn
 
f= fij

..
   

 .

  0 
(fit )i∈P(t) +v

18
II. Problème de flot maximal dans un graphe

2) Théorème de Ford-Fulkerson

L. R. Ford (1927– 2017) D. R. Fulkerson (1924–1976)

Ford, L. R., Jr. ; Fulkerson, D. R. (1956), Maximal flow through a network,

Canadian Journal of Mathematics 8 : 399–404.
L. R. Ford ; D. R. Fulkerson (1962). Flows in Networks.

19
II. Problème de flot maximal dans un graphe

Définition
Une coupe d’un graphe valué G = (E , Γ, c) possédant un seul sommet
source s et un seul sommet puits t, est une partition des sommets notée
(X , X ) telle que :

E =X ∪X
X ∩X =∅
s ∈ X et t ∈ X
X
La capacité de la coupe est définie par c(X , X ) = cij
i∈X
j∈X

20
 X
X a 2 c
10 6
s 4 3
t
3 4
b 5 d

Capacité de la coupe c(X , X ) = 10 + 3 + 4 = 17.

21
On peut comparer la valeur d’un flot avec la capacité d’une coupe du
graphe.

Théorème de Ford-Fulkerson
Soit G = (E , Γ, c) un graphe valué. Pour tout flot réalisable f et toute
coupe (X , X ), on a
v (f ) ≤ c(X , X )
où v (f ) est la valeur du flot f .

22
Le théorème de Ford-Fulkerson permet de savoir si un flot est maximal ou
non. Par exemple :

X
X 2
a 2 c
4
10 6 3
4 2 1 3
s t
3 4 v(f)=7
3 4
b 5 d
5

v (f ) = 7 et c(X , X ) = 7 ⇒ flot maximal.

23
Démonstration du théorème de Ford-Fulkerson

Convention : si l’arête (i, j) n’existe pas dans le graphe, on pose fij = 0.

X X
⇒ v (f ) = fsj = fsj .
j∈S(s) j∈E

On montre que
X X
v (f ) = fij − fki
i∈X i∈X
 j∈X k∈X I
@
@
@
flot de X à X flot de X à X
X
⇒ v (f ) ≤ cij = c(X , X )
i∈X
j∈X

24
 X X
Démonstration de la relation v (f ) = fij − fki .
i∈X i∈X
j∈X k∈X

X X
D’après la conversation des flux : fij − fki = 0 pour tout i 6= s, t.
j∈E k∈E
XX X 
On somme sur i ∈ X , i 6= s : fij − fki = 0
i∈X j∈E k∈E
i6=s
soit XX X  X X
fij − fki − fsj − fks = 0.
|{z}
i∈X j∈E k∈E j∈E k∈E =0
| {z }
=v (f )
On obtient
X X X X X X
v (f )v = fij +
 fij − fki − fki = fij − fki
i∈X
 i∈X i∈X i∈X i∈X i∈X
j∈X
 j∈X k∈X k∈X j∈X k∈X


25
II. Problème de flot maximal dans un graphe

3) Coupe minimale
Le Théorème de Ford-Fulkerson admet un corollaire qui donne une
condition suffisante pour avoir un flot maximal.
On dit qu’une arête (i, j) ∈ Γ est saturée si fij = cij et qu’elle est
insaturée si fij = 0

Définition
Une coupe (X , X ) est dite minimale pour f si toute arête de X vers X est
saturée et toute arête de X vers X est insaturée.

26
Coupe minimale (X , X )

X
X
8
b 12
10
8

a 2 2

c 3 d
0

arêtes (a, b) et (c, b) saturées

arête (d, c) insaturée

27
Proposition
S’il existe une coupe minimale pour un flot f , alors ce flot est maximal.

Preuve. A partir de la formule établie dans le th. de Ford-Fulkerson :

=cij =0
X z}|{ X z}|{
v (f ) = fij − fki = c(X , X )
i∈X i∈X
j∈X k∈X

⇒ v (f ) est maximal. 

28
Coupe minimale / flot maximal

X
X
b 12 e
8 10 5
8 5

a 6 t
2 2 5
5
9 8 5
c 3 d
7 0
s 2

⇒ flot maximal v (f ) = c(X , X ) = 10

29
III. Algorithme de Ford-Fulkerson
1) Condition nécessaire et suffisante de flot maximal

Définition 1.
Une chaîne d’un graphe est une suite de sommets

C = (i1 , i2 , · · · , ip , ip+1 , · · · , iq )

reliés entre eux par des arêtes c’est-à-dire tels que

(ip , ip+1 ) ∈ Γ ou (ip+1 , ip ) ∈ Γ

(arête directe) (arête inverse)

Une chaîne ne tient pas compte de l’orientation des arêtes reliant les
sommets (chaîne 6= chemin).
1 c12 2 c32 c43
3 4
30
Définition 2.
Soit G = (E , Γ, c) un graphe valué possédant une seule source s et un seul
puits t. Une chaîne C = (s, i1 , i2 , · · · , ip , ip+1 , · · · , iq , t) est dite
améliorante pour un flot réalisable f donné si :
f (ip , ip+1 ) < c(ip , ip+1 ) si (ip , ip+1 ) ∈ Γ (arête directe)
f (ip+1 , ip ) > 0 si (ip+1 , ip ) ∈ Γ (arête inverse)

Remarque : ce qui compte ici, ce sont les inégalites strictes.

(0) 1 1 3 2 (3)

s v=5
4 3 3 t (v=6)
2 (3) 3
31
L’algorithme de Ford-Fulkerson permet de trouver un flot maximal par
recherche de chaînes améliorantes. Il est basé sur le résultat suivant :
Théorème
Un flot réalisable est maximal si et seulement s’il n’existe pas de chaîne
améliorante.

32
L’algorithme de Ford-Fulkerson permet de trouver un flot maximal par
recherche de chaînes améliorantes. Il est basé sur le résultat suivant :
Théorème
Un flot réalisable est maximal si et seulement s’il n’existe pas de chaîne
améliorante.
Preuve.
i) Condition nécessaire
Soit f un flot réalisable maximal. On suppose par l’absurde qu’il existe une
chaîne améliorante C = (s, i1 , i2 , · · · , ip , ip+1 , · · · , iq , t). On note

ε1 = min{c(ip , ip+1 ) − f (ip , ip+1 ) tel que (ip , ip+1 ) ∈ Γ (arête directe)}
ε2 = min{f (ip+1 , ip ) tel que (ip+1 , ip ) ∈ Γ (arête inverse)}

→ ε = min{ε1 , ε2 } > 0
ε représente l’amélioration qu’on peut apporter au flot.

32
Nouveau flot f 0 qui coïncide avec f en dehors de la chaîne améliorante. Sur
les arêtes de la chaîne :
Si (ip , ip+1 ) ∈ Γ (arête directe) alors

f 0 (ip , ip+1 ) = f (ip , ip+1 ) + ε

Si (ip+1 , ip ) ∈ Γ (arête inverse) alors

f 0 (ip , ip+1 ) = f (ip , ip+1 ) − ε

+ε −ε
ip−1 ip ip+1

33
Le nouveau flot f 0 est bien réalisable. En particulier, il y a
conservation des flux en chaque sommet : 4 cas possibles

ip ip
+ε +ε +ε −ε

ip−1 ip+1 ip−1 ip+1

ip ip
−ε +ε −ε −ε

ip−1 ip+1 ip−1 ip+1

34
 Le nouveau flot f 0 est augmenté de +ε quand il arrive au puits t :
v (f 0 ) = v (f ) + ε.

+ε +ε
s i1 iq t

⇒ le flot f n’est pas maximal ⇒ contradiction. 

35
ii) Condition suffisante
On suppose qu’il n’existe pas de chaîne améliorante. On va montrer que le
flot est maximal en trouvant une coupe (X , X ) telles que v (f ) = c(X , X )
(Th. Ford-Fulkerson).
Construction de la coupe (X , X )
X est l’ensemble des sommets qui sont marqués de la façon suivante :
1 On marque la source s
2 A partir de tous les sommets i marqués, marquer tous les sommets j
non encore marqués tels que

f (i, j) < c(i, j) (arête directe) ou f (j, i) > 0 (arête inverse)

3 Recommencer en 2) jusqu’à ce qu’il n’y ait plus de marquage possible.

⇒ A l’issue du marquage, on a v (f ) = c(X , X ). 

36
Remarque : le puits t ne peut pas être marqué sinon il y aurait une chaîne
améliorante.

37
III. Algorithme de Ford-Fulkerson
2) Algorithme de Ford-Fulkerson

Initialisation par un flot initial réalisable (f = 0)

Tant que le flot n’est pas maximal
Marquage de la source s
Tant qu’on marque des sommets
Pour tout sommet marqué i
Marquer les sommets j non marqués tq
f (i, j) < c(i, j) ou f (j, i) > 0
Fin pour
Fin Tant que
Si le puits t n’est pas marqué alors le flot est maximal
Sinon amélioration du flot
Fin Tant que

38
III. Algorithme de Ford-Fulkerson

Amélioration du flot
trouver une chaîne qui a permis de marquer t et calculer
ε = min(ε1 , ε2 ) > 0 avec

ε1 = min {c(ip , ip+1 ) − f (ip , ip+1 ) avec (ip , ip+1 ) ∈ Γ (arête directe)}
ε2 = min {f (ip+1 , ip ) avec (ip+1 , ip ) ∈ Γ (arête inverse)}

trouver le nouveau flot f 0 :

Si (ip , ip+1 ) ∈ Γ (arête directe) alors f 0 (ip , ip+1 ) = f (ip , ip+1 ) + ε
Si (ip+1 , ip ) ∈ Γ (arête inverse) alors f 0 (ip , ip+1 ) = f (ip , ip+1 ) − ε

39
III. Algorithme de Ford-Fulkerson

3) Parcours de graphe
Parcours profondeur (DFS)

40
III. Algorithme de Ford-Fulkerson

3) Parcours de graphe
Parcours profondeur (DFS)
Exploration en profondeur des chemins : pour chaque sommet, on
prend et on marque le premier sommet successeur jusqu’à ce qu’un
sommet n’ait plus de successeur ou bien que tous ses successeurs
soient déjà marqués.

40
III. Algorithme de Ford-Fulkerson

3) Parcours de graphe
Parcours profondeur (DFS)
Exploration en profondeur des chemins : pour chaque sommet, on
prend et on marque le premier sommet successeur jusqu’à ce qu’un
sommet n’ait plus de successeur ou bien que tous ses successeurs
soient déjà marqués.
On utilise généralement une pile pour l’exploration des sommets.

40
III. Algorithme de Ford-Fulkerson

3) Parcours de graphe
Parcours profondeur (DFS)
Exploration en profondeur des chemins : pour chaque sommet, on
prend et on marque le premier sommet successeur jusqu’à ce qu’un
sommet n’ait plus de successeur ou bien que tous ses successeurs
soient déjà marqués.
On utilise généralement une pile pour l’exploration des sommets.

Utilisations :
Pour un graphe non-orienté, calcul des composantes connexes.
Pour un graphe orienté sans cycle, tri topologique des sommets : ordre
des sommets tel qu’un sommet est toujours visité avant ses successeurs.
En dépilant, on obtient un tri topologique (en ordre inverse).

40
III. Algorithme de Ford-Fulkerson

Parcours largeur (BFS)

41
III. Algorithme de Ford-Fulkerson

Parcours largeur (BFS)

A partir d’un sommet, on liste et on marque tous les sommets
successeurs non encore marqués, jusqu’à ce qu’un sommet n’ait plus
de successeur ou bien que tous ses successeurs soient déjà marqués.

41
III. Algorithme de Ford-Fulkerson

Parcours largeur (BFS)

A partir d’un sommet, on liste et on marque tous les sommets
successeurs non encore marqués, jusqu’à ce qu’un sommet n’ait plus
de successeur ou bien que tous ses successeurs soient déjà marqués.
On utilise généralement une file (liste FIFO) pour l’exploration des
sommets.

41
III. Algorithme de Ford-Fulkerson

Parcours largeur (BFS)

A partir d’un sommet, on liste et on marque tous les sommets
successeurs non encore marqués, jusqu’à ce qu’un sommet n’ait plus
de successeur ou bien que tous ses successeurs soient déjà marqués.
On utilise généralement une file (liste FIFO) pour l’exploration des
sommets.

Utilisations :
Le parcours en largeur explore tous les sommets accessibles depuis le
sommet initial ⇒ calcul des composantes connexes.
Recherche du plus court chemin (nb minimum d’arêtes) entre deux
sommets.

41
III. Algorithme de Ford-Fulkerson
Algorithme BFS et plus court chemin
Initialement, tous les sommets sont non-marqués et la file est
vide.
Marquer et insérer le sommet s de départ dans la file.
Initialisation de la distance D(s) = 0.
Tant que la file n’est pas vide
- Supprimer le sommet P situé en tête de file.
- Pour chaque successeur non marqué Q de P,
- Marquer et insérer Q dans la file
- Calcul de la distance de Q à s : D(Q) = D(P) + 1.
Fin Pour
Fin Tant que

42
III. Algorithme de Ford-Fulkerson
Algorithme BFS et plus court chemin
Initialement, tous les sommets sont non-marqués et la file est
vide.
Marquer et insérer le sommet s de départ dans la file.
Initialisation de la distance D(s) = 0.
Tant que la file n’est pas vide
- Supprimer le sommet P situé en tête de file.
- Pour chaque successeur non marqué Q de P,
- Marquer et insérer Q dans la file
- Calcul de la distance de Q à s : D(Q) = D(P) + 1.
Fin Pour
Fin Tant que

+ On obtient la liste des sommets accessibles à partir de s (sommets

marqués) et D est la distance la plus courte (nb minimum d’arêtes)
de chaque sommet à s.
42
Exemple de parcours DFS / BFS

Parcours profondeur DFS : A,B,E,F,C,G,D (tri topologique A,D,C,G,B,F,E)

Parcours largeur BFS : A,B,C,D,E,F,G

43
III. Algorithme de Ford-Fulkerson

Remarque. Dans la recherche d’une chaîne améliorante de l’algorithme de

Ford Fulkerson, le parcours du graphe se fait en considérer non pas les
successeurs d’un sommet mais les sommets voisins accessibles au sens
d’une chaîne améliorante.

4) Un exemple
Considérations pratiques :
Dans la pratique, on utilise plusieurs tableaux
E = {sommets marqués mais non complètement examinés}
tableau orig qui indique l’origine du marquage :
arête directe (ip , ip+1 ) ∈ Γ → orig (ip+1 ) = ip
arête inverse (ip+1 , ip ) ∈ Γ → orig (ip ) = −ip+1
tableau ε : amélioration possible du flot à chaque marquage.

44
 1 2
a 3 b
1 2
1 2
2 2
1 0 1
s t
2 1 v=1
1 1 v=2
c v=3 = max(v)
Marquage pile profondeur (DFS)

45
 1 2
a 3 b
1 2
1 2
2 2
1 0 1
s t
2 1 v=1
1 1 v=2
c v=3 = max(v)
Marquage pile profondeur (DFS)
Etape 1 :
E s a b c t
orig − s a b c
ε ∞ 2 2 1 ε=1

45
 1 2
a 3 b
1 2
1 2
2 2
1 0 1
s t
2 1 v=1
1 1 v=2
c v=3 = max(v)
Marquage pile profondeur (DFS)
Etape 1 : Etape 2 :
E s a b c t E s a b t
orig − s a b c orig − s a b
ε ∞ 2 2 1 ε=1 ε ∞ 1 1 ε=1

45
 1 2
a 3 b
1 2
1 2
2 2
1 0 1
s t
2 1 v=1
1 1 v=2
c v=3 = max(v)
Marquage pile profondeur (DFS)
Etape 1 : Etape 2 :
E s a b c t E s a b t
orig − s a b c orig − s a b
ε ∞ 2 2 1 ε=1 ε ∞ 1 1 ε=1
Etape 3 :
E s c b a t
orig − s −c −b b
ε ∞ 2 1 1 ε=1
on dépile ↑ 45
 Etape 4 :
E s c
⇒ pile vide (E = ∅).
orig − s
ε ∞ 1
on dépile ↑ ↑
Le puits t n’est pas marqué ⇒ pas de chaîne améliorante ⇒ flot maximal

46
 Etape 4 :
E s c
⇒ pile vide (E = ∅).
orig − s
ε ∞ 1
on dépile ↑ ↑
Le puits t n’est pas marqué ⇒ pas de chaîne améliorante ⇒ flot maximal
Coupe minimale : (X , X ) avec X = {s, c} et X = {a, b, t}.
X est formé des sommets marqués à la dernière étape (pile vide).
2
a 3 b
2 2
2 2
0 1
s t
2 1 max(v)=3
1 1
c
X X
46
III. Algorithme de Ford-Fulkerson
5) Finitude et complexité
Capacités à valeurs entières
Pour des capacités à valeurs entières, l’algorithme de Ford-Fulkerson
converge en un nombre fini d’opérations.

47
III. Algorithme de Ford-Fulkerson
5) Finitude et complexité
Capacités à valeurs entières
Pour des capacités à valeurs entières, l’algorithme de Ford-Fulkerson
converge en un nombre fini d’opérations.
Pour un graphe avec n sommets et m arêtes :
O(m) opérations pour la recherche d’une chaîne améliorante et
l’amélioration du flot.
La capacité d’une coupe est au plus en O(n × Cmax ) où Cmax est le
maximum des capacités des arêtes. Dans le pire des cas, le flot
augmente d’une seule unité à chaque fois. Il y a donc au plus
O(nCmax ) améliorations.

⇒ O(nmCmax ) opérations pour l’algorithme de Ford-Fulkerson.

47
III. Algorithme de Ford-Fulkerson
5) Finitude et complexité
Capacités à valeurs entières
Pour des capacités à valeurs entières, l’algorithme de Ford-Fulkerson
converge en un nombre fini d’opérations.
Pour un graphe avec n sommets et m arêtes :
O(m) opérations pour la recherche d’une chaîne améliorante et
l’amélioration du flot.
La capacité d’une coupe est au plus en O(n × Cmax ) où Cmax est le
maximum des capacités des arêtes. Dans le pire des cas, le flot
augmente d’une seule unité à chaque fois. Il y a donc au plus
O(nCmax ) améliorations.

⇒ O(nmCmax ) opérations pour l’algorithme de Ford-Fulkerson.

Pour des capacités à valeurs réelles et un parcours en largeur (BFS),

l’algorithme converge également.
47
6) Variante : Algorithme d’Edmonds-Karp (1972).

C’est une implémentation particulière de l’algorithme de Ford-Fulkerson en

parcours largeur (BFS) et qui consiste à toujours choisir une chaine
améliorante de plus court chemin de s à t, c’est-à-dire celle avec le moins
d’arêtes possibles.
Cet algorithme se termine toujours (même pour des capacités non entières,
contrairement à Ford-Fulkerson...) avec une complexité en O(nm2 ) (indép.
des capacités).

48
IV. Flot maximal avec bornes inférieures et supérieures
1) Introduction
Graphe valué par des capacités inférieures {αij } et supérieures {βij } :
G = (E , Γ, ({αij }, {βij }))
On note :

49
IV. Flot maximal avec bornes inférieures et supérieures
1) Introduction
Graphe valué par des capacités inférieures {αij } et supérieures {βij } :
G = (E , Γ, ({αij }, {βij }))
On note :

Problème de flot maximal généralisé :

max [F = v ]
fij ,v
 X

 fsk − v = 0 (source s)



 k∈S(s)
 X X
 − fij + fjk = 0, ∀j 6= s, t



i∈P(j) k∈S(j)
X
− fit + v = 0 (puits t)





i∈P(t)




 αij ≤ fij ≤ βij pour toute arête (i, j) ∈ Γ

49
IV. Flot maximal avec bornes inférieures et supérieures
2) Condition nécessaire d’existence d’un flot réalisable pour G .

Proposition
S’il existe un flot {fij } réalisable sur G vérifiant αij ≤ fij ≤ βij pour tout
(i, j) ∈ Γ, alors pour tout j 6= s, t :
X X
αij ≤ βjk (1)
i∈P(j) k∈S(j)
X X
αjk ≤ βij (2)
k∈S(j) i∈P(j)

Démonstration. Soit j 6= s, t. On somme la relation αij ≤ fij ≤ βij sur

i ∈ P(j) puis sur j ∈ S(i) :
X X X X
αij ≤ fij = fjk ≤ βjk .
i∈P(j) i∈P(j) k∈S(j) k∈S(j)

L’inégalité (2) se montre de la même façon. 

50
IV. Flot maximal avec bornes inférieures et supérieures
3) Adaptation de Ford-Fulkerson : flot maximal sur G .
On suppose qu’on dispose d’un flot initial réalisable sur G (cf. section
suivante). On adapte l’algorithme de Ford-Fulkerson pour la recherche
d’une chaine améliorante. On détermine ainsi un flot maximal sur G .

arête directe arête inverse

condition d’amélioration : fij < βij fij > αij
amélioration possible : ε1 = βij − fij > 0 ε2 = fij −αij > 0

51
IV. Flot maximal avec bornes inférieures et supérieures
4) Recherche d’un flot réalisable sur G : graphe auxiliaire G 0 .
Il reste à déterminer un flot réalisable initial f sur G . On ne peut plus
prendre f ≡ 0 partout sur G !
On se ramène au cas d’un flot positif par le changement de variable
fij0 = fij − αij pour tout (i, j) ∈ Γ,
et le nouveau flot vérifie 0 ≤ fij0 ≤ cij0 avec

cij0 = βij − αij

52
IV. Flot maximal avec bornes inférieures et supérieures
4) Recherche d’un flot réalisable sur G : graphe auxiliaire G 0 .
Il reste à déterminer un flot réalisable initial f sur G . On ne peut plus
prendre f ≡ 0 partout sur G !
On se ramène au cas d’un flot positif par le changement de variable
fij0 = fij − αij pour tout (i, j) ∈ Γ,
et le nouveau flot vérifie 0 ≤ fij0 ≤ cij0 avec

cij0 = βij − αij

on n’a plus conservation du flux pour {fij0 }...

52
IV. Flot maximal avec bornes inférieures et supérieures
Pour assurer la conservation du nouveau flux aux sommets, on introduit un
graphe valué auxiliaire G 0 = (E 0 , Γ0 , c 0 ) :

53
IV. Flot maximal avec bornes inférieures et supérieures
Pour assurer la conservation du nouveau flux aux sommets, on introduit un
graphe valué auxiliaire G 0 = (E 0 , Γ0 , c 0 ) :
On ajoute deux sommets s 0 et t 0 : E 0 = E ∪ {s 0 , t 0 }

53
IV. Flot maximal avec bornes inférieures et supérieures
Pour assurer la conservation du nouveau flux aux sommets, on introduit un
graphe valué auxiliaire G 0 = (E 0 , Γ0 , c 0 ) :
On ajoute deux sommets s 0 et t 0 : E 0 = E ∪ {s 0 , t 0 }
On ajoute des arêtes reliant s 0 aux sommets j 6= s et des arêtes reliant
les sommets j 6= t à t 0 :
Γ0 = Γ ∪ {(s 0 , j), ∀j ∈ E , j 6= s} ∪ {(j, t 0 ), ∀j ∈ E , j 6= t}
Pour éviter d’avoir 2 sources s et s 0 et 2 puits t et t 0 , on relie t à s
par un arc de capacité infinie (s et t sont confondus pour G 0 ).

53
IV. Flot maximal avec bornes inférieures et supérieures
Pour assurer la conservation du nouveau flux aux sommets, on introduit un
graphe valué auxiliaire G 0 = (E 0 , Γ0 , c 0 ) :
On ajoute deux sommets s 0 et t 0 : E 0 = E ∪ {s 0 , t 0 }
On ajoute des arêtes reliant s 0 aux sommets j 6= s et des arêtes reliant
les sommets j 6= t à t 0 :
Γ0 = Γ ∪ {(s 0 , j), ∀j ∈ E , j 6= s} ∪ {(j, t 0 ), ∀j ∈ E , j 6= t}
Pour éviter d’avoir 2 sources s et s 0 et 2 puits t et t 0 , on relie t à s
par un arc de capacité infinie (s et t sont confondus pour G 0 ).
Capacité c 0 :
cij0 = βij − αij , ∀(i, j) ∈ Γ
X
cs0 0 j = αij , ∀j 6= s
i∈P(j)
X
cjt0 0 = αjk , ∀j 6= t
k∈S(j)

53
IV. Flot maximal avec bornes inférieures et supérieures

0
fjk = fjk ↵jk

i c0ij j c0jk k
0
fij = fij ↵ij

54
IV. Flot maximal avec bornes inférieures et supérieures

s′

c0s0 j
0
fjk = fjk ↵jk

i c0ij j c0jk k
0
fij = fij ↵ij
c0jt0

t′

54
IV. Flot maximal avec bornes inférieures et supérieures

s′

c0s0 j = +↵ij
0
fjk = fjk ↵jk

i c0ij j c0jk k
0
fij = fij ↵ij
c0jt0 = +↵jk

t′

54
IV. Flot maximal avec bornes inférieures et supérieures

s′ c0s0 t t

c0s0 j = +↵ij
0
fjk = fjk ↵jk

i c0ij j c0jk k
0
fij = fij ↵ij
c0jt0 = +↵jk

t′
c0st0
s
54
IV. Flot maximal avec bornes inférieures et supérieures

s′ c0s0 t t s

c0s0 j = +↵ij
0
fjk = fjk ↵jk

i c0ij j c0jk k
0
fij = fij ↵ij
c0jt0 = +↵jk

t′
c0st0
t s
54
IV. Flot maximal avec bornes inférieures et supérieures

Soient f : Γ → R et f 0 : Γ0 → R telles que

fij0 = fij − αij , ∀(i, j) ∈ Γ

X
fs00 j = cs0 0 j := αij , ∀j ∈ E , j 6= s
i∈P(j) (3)
X
fjt0 0 = cjt0 0 := αjk , ∀j ∈ E , j 6= t
k∈S(j)

{fij0 } est tel que toutes les arêtes (s 0 , j) et (i, t 0 ) sont saturées, ∀j 6= s 0 ,
∀i 6= t 0 .

55
IV. Flot maximal avec bornes inférieures et supérieures

Théorème (CNS d’existence d’un flot réalisable sur G )

Soient f : Γ → R et f 0 : Γ0 → R vérifiant (3). Alors,
1 pour tout j ∈ E , j =
6 s, j =
6 t,
X X X X
− fij + fjk = − fij0 + fjk0 (4)
i∈P(j) k∈S(j) i∈P 0 (j) k∈S 0 (j)

où P 0 (j) (resp. S 0 (j)) désigne les prédécesseurs (resp. successeurs)

dans E 0 du sommet j.
2 {fij } est un flot réalisable sur G ⇔ {fij0 } est un flot maximal sur G 0

56
IV. Flot maximal avec bornes inférieures et supérieures

Démonstration
1 Soit j ∈ E , j 6= s, t. Par définition de {fij0 }, on a
X X X X
− fij + fjk = − fij0 − αij
i∈P(j) k∈S(j) i∈P(j) i∈P(j)
| {z }
=fs00 j
X X
+ fjk0 + αjk
k∈S(j) k∈S(j)
| {z }
=fjt0 0
X X
= − fij0 + fjk0
i∈P 0 (j) k∈S 0 (j)

57
IV. Flot maximal avec bornes inférieures et supérieures

2 i) Condition suffisante.
Soit {fij0 } un flot maximal sur G 0 . D’après (1), {fij } est un flot sur G et
pour tout (i, j) ∈ Γ,

0 ≤ fij0 ≤ cij0 := βij − αij ⇒ αij ≤ fij = fij0 + αij ≤ βij

donc {fij } est un flot réalisable sur G .

58
IV. Flot maximal avec bornes inférieures et supérieures

2 i) Condition suffisante.
Soit {fij0 } un flot maximal sur G 0 . D’après (1), {fij } est un flot sur G et
pour tout (i, j) ∈ Γ,

0 ≤ fij0 ≤ cij0 := βij − αij ⇒ αij ≤ fij = fij0 + αij ≤ βij

donc {fij } est un flot réalisable sur G .

ii) Condition nécessaire.
Soit {fij } un flot réalisable sur G . Alors d’après (1), {fij0 } est un flot sur
G 0 . De plus, il est réalisable (0 ≤ fij0 ≤ cij0 := βij − αij ). Par
construction,
toutes les arêtes de G 0 qui partent de s 0 sont saturées pour {fij0 }.
toutes les arêtes de G 0 qui arrivent en t 0 sont saturées.
Il n’y a donc plus de chaîne améliorante possible ⇒ {fij0 } est un flot
maximal sur G 0 .

58
IV. Flot maximal avec bornes inférieures et supérieures

Pour trouver un flot réalisable pour G , il faut donc déterminer un flot

maximal pour le graphe auxiliaire G 0 . On utilise pour cela l’algorithme de
Ford-Fulkerson (dans sa version standard) sur G 0 .
Flot réalisable initial sur le graphe auxiliaire G 0 .
Comme flot initial sur G 0 on peut choisir le flot nul f 0 ≡ 0 mais on peut
aussi faire un peu mieux :

fs00 j = fjt0 0 = min(cs0 0 j , cjt0 0 ) pour tout j ∈ E

fij0 = 0 pour tout (i, j) ∈ Γ

59
IV. Flot maximal avec bornes inférieures et supérieures

Exemple de détermination d’un flot réalisable initial sur G .

60
IV. Flot maximal avec bornes inférieures et supérieures
a) Graphe auxiliaire G 0 :

3
7

2
s t

3
4

61
IV. Flot maximal avec bornes inférieures et supérieures
a) Graphe auxiliaire G 0 :

a
4
3
33
7

2
s′ s t t′

3
4
2
b 1

4
61
IV. Flot maximal avec bornes inférieures et supérieures
a) Graphe auxiliaire G 0 :

a
4
3 s
33
7

2
s′ s t t′

3
4
t 2
b 1

4
61
IV. Flot maximal avec bornes inférieures et supérieures
b) Flot réalisable initial sur G 0 :

a
4
3 s
3
7
0 0
2
s′ s t t′
0

0
3
4 0

t 2
b 1

4
62
IV. Flot maximal avec bornes inférieures et supérieures
b) Flot réalisable initial sur G 0 :

a
4
3 s
3
7
0 0
2
s′ s t t′
0

0
3
4 0 1

t 2
b 1
1

4
62
IV. Flot maximal avec bornes inférieures et supérieures
b) Flot réalisable initial sur G 0 :

a
4
3 s
3
3 3
7
0 0
2
s′ s t t′
0

0
3
4 0 1

t 2
b 1
1

4
62
IV. Flot maximal avec bornes inférieures et supérieures
b) Flot réalisable initial sur G 0 :

4
4

a
4
3 s
3
3 3
7
0 0
2
s′ s t t′
0

0
3
4 0 1

t 2
b 1
1

4
62
IV. Flot maximal avec bornes inférieures et supérieures
c) Flot maximal sur G 0 (Ford-Fulkerson) :

4
4

a
4
3 s
3
3 4
7
1 0
2
s′ s t t′
0

0
3
4 1 1

t 2
b 1
2

4
4 63
IV. Flot maximal avec bornes inférieures et supérieures
d) Flot réalisable sur G :

3
10
3 4 3

6
1
s 1 t
3
1 5
4 1
1 2
b

64