Université IBN Tofail
Faculté des Sciences
Département Informatique
Recherche Opérationnelle :
Flot maximal
Author: Filière:
Pr. Khalil IBRAHIMI Licence SMI, S5
December 30, 2021
FSK, SMI, S5 Cours Flot maximal
1 Problèmes du flot maximum
Exemple du réseau de transport Une usine S
Trois demandes en F (30), G (16) et H (15) (en conteneurs)
Des disponibilités d’un réseau de transport
Comment satisfaire au mieux la demande ?
Définition d’un flot
• On appelle un réseau de transport un graphe orienté fini de sommets
sans boucles avec une source s et une puits t , G=(X, U).
• Chaque arc a une capacité c(u) (valeure de l’arc = débit max).
• Au plus un arc entre deux sommets.
• Un flot dans un réseau G est une fonction à valeur entier f: X x X —
R tel que:
- Une loi de conservation aux sommets intermédiaires x différent de s
et de t. X X
f (a, x) = f (b, x)
a∈P (x) b∈S(x)
- Contrainte de capacité: Le flux d’un arc u est f (u) (0 ≤ f (u) ≤ c(u))
- Symétrie : pour tout i, j ∈ XxX, on a f (i, j) = −f (j, i)
• La valeur du flot est la somme des flux entrant à t:
X X
V (f ) = f (x, t) = f (x, s)
x∈P (t) x∈S(s)
Modélisation
Pr. Khalil IBRAHIMI 1 a.u: 2021-2022
FSK, SMI, S5 Cours Flot maximal
Chaine améliorante
• Un arc u est sturé si f (u) = c(u).
• Si l’arc u ∈
/ U , f (u) = 0.
• Une chaine améliorante est une chaine élémentaire de la source s à la
destination t (puits) telle que : aucun arc direct ne soit saturé et que
les flux des arcs indirects soient strictements positifs.
• L’algorithme de Ford-Fulkerson permet de trouver une chaine améliorante
et d’augmenter la valeur du flot.
• La recherche d’une chaı̂ne améliorante = phase de marquage
• Amélioration du flot = dans la phase d’augmentation
Réseaux résiduels (Graphe d’écarts)
• Capacité résiduel d’un arc = la quantité de flux supplémentaire à
ajouter sans dépasser la capacité de l’arc:
cf (u) = c(u) − f (u)
• Le réseau résiduel de G=(X, U) et un flot f, est constitué des arcs de
G qui peuvent supporter un flux supplémentaire (Gf = (X, U 0 )) avec
pour tout u ∈ U 0 , cf (u) > 0
Ajouter un flot au flot existant Soit un flot f de G=(X, U) et un flot f’ de
Gf = (X, U 0 ). Alors la somme f + f 0 est un flot de G de valeur |f + f 0 |
=|f | + |f 0 |
Chemin améliorant Définition Un chemin p améliorant du graphe G de
flot f est un chemin élémentaire de s vers t dans le réseau résiduel Gf .
Pr. Khalil IBRAHIMI 2 a.u: 2021-2022
FSK, SMI, S5 Cours Flot maximal
La cpacité résiduelle de p est la quantité maximale transportée via les arcs
du chemin p :
cf (p) = min{cf (u) : u ∈ p}
Lemme Soit G=(X, F) un réseau de transport, soit f un flot de G et soit p
un chemin améliorant de Gf . On définit un efonction fp :
fp (u) = cf (p)siu ∈ p, −cf (p)siu ∈ p(inverse), sinon0
Alors fp est un flot de Gf de valeur |fp | = cf (p) > 0
Coupe
• Soient X1 un ensemble de sommets de G, et X2 = X−X1 son complémentaire
dans G tellle que s ∈ X1 et t ∈ X2 . La coupe de G est C = (X1 , X2 ) =
{u/u ∈ X1 xX2 }.
• Elle sépare un sommet a d’un sommet b lorsque a ∈ X1 et b ∈ X2 .
• Si f est un flot de G, alors le flot net à travers la coupure (X1 , X2 ) est
f (X1 , X2 )
• La capacité de la coupe est notée c(C) = u∈(X1 xX2 ) c(u).
P
• Une coupe minimum d’un réseau est une coupe dont la capacité est
minimale à toutes les coupes du réseau.
• La coupe inverse de C est C 0 = {u/u ∈ X2 xX1 }
• Le flot est compatible si pour tout u , f (u) ≤ c(u)
• Un flot est complet si tous les chemins de s à t sont saturés.
Lemme Pour tout flot f compatible et tout coupe C séparant s et t, la valeur
du flot v(f ) = f (C) − f (C 0 ).
Aussi v(f ) ≤ c(C)
L’égalité implique la maximalité du flot et la minimalité de la coupe.
Flot maximum et coupe minimum Théorème Si f est un flot dans G d
source s et de puits t alors les contitions suivantes sont équivalentes:
• f est un flot maximam de G
Pr. Khalil IBRAHIMI 3 a.u: 2021-2022
FSK, SMI, S5 Cours Flot maximal
• Gf ne contient aucun chemin améliorant
• |f | = c(X1 , X2 ) pour la coupe de G.
Algorithme Ford-Fulkerson: Phase de marquage
Marquer la source s par +
Tant que cela est possible
Choisir un sommet x non marqué vérifiant l’une des deux conditions:
si il exite y ∈ X tel que :
y est marqué et y ∈ P (x))et(f (y, x) < c(y, x)
Alors marquer + le sommet x.
S’il exsite y ∈ X tel que :
y est marqué et y ∈ S(x))et(f (y, x) > 0
Alors marquer - le sommet x.
Noté Γp (x) = y: Prédécesseur de x dont le marquage est y.
Si le puits t est marqué on s’arrête et le flot actuel n’est pas maximal. La
chaine améliorante est trouvée.
Si le puits t n’est pas marqué, alors la chaine n’existe pas.
Algorithme Ford-Fulkerson: Phase d’augmentation
Tant que qu’il existe une chaı̂ne améliorante p faire
Augmenter le flux sur la chaine améliorante comme suit:
• δ + = min{c(u) − f (u)}, pour tout arc direct u de p.
• δ − = min(f (u)), pour tout arc indirect u de p.
• δ − = min{δ − , δ + }
• pour tout arc direct u faire : f (u) = f (u) + δ
• pour tout arc indirect u faire : f (u) = f (u) − δ
Lorsque n’existe pas de chaine améliorante, le flot est optimal.
Flot de départ (f0 ) LE flot intial est de valeur V (f0 ) = 37.
Pr. Khalil IBRAHIMI 4 a.u: 2021-2022
FSK, SMI, S5 Cours Flot maximal
Montrer que le chemin améliorant
est p =(S, C, G, F, et P) et cf (p) = 4
Augmentation du flot f0
Montrer que le flot
maximal est 57 à la fin de l’algorithme.
Pr. Khalil IBRAHIMI 5 a.u: 2021-2022
