Chapitre 8 : Flots dans les r eseaux - LIPN – …lipn.univ-paris13.fr/~borne/Docs/Graphes_chap8_Flots...Plan 1 Flot r ealisable 2 Le probl eme du ot maximum Exemple Plusieurs sources,

Chapitre 8 : Flots dans les reseauxAlgorithmique de graphes

Sup Galilee-INFO2

Sylvie Borne

2011-2012

Chapitre 8 : Flots dans les reseaux - 1/57

Plan1 Flot realisable

2 Le probleme du flot maximumExemplePlusieurs sources, plusieurs puitsFlot maximum et programmation lineaire

3 Chaınes augmentantes

4 Algorithme de Ford et Fulkerson (1961)Procedure de marquage (labelling)Algorithme de la chaıne augmentanteAlgorithme de Ford et Fulkerson

5 La coupe minimum

6 Implementation et complexite de l’algorithme de Ford etFulkerson


Probleme de flot

Probleme de plus court chemin→ une personne seule de la source a la destination.

Probleme de flot→ acheminement d’une quantite de marchandises (divisibles : onpeut acheminer nos marchandises par des routes differentes) de lasource vers la destination.


Probleme de flot : Applications

Applications :

logistique : transport de marchandises : train, camion,bateau,. . .

distribution d’eau (canalisations)

transport de petrole : reseaue de pipelines

energie : reseau EDF, centrales → clients

information : reseau telephonique, reseau d’entreprises,internet.


Reseau de transport

Definition : reseau de transportUn reseau de transport note R = (G = (V , ~E ), s, t, c) est forme

de :

G = (V , ~E ) un graphe oriente

s ∈ V appele sommet source

t ∈ V appele sommet destination ou puits

c : ~E → N,Q+ fonction capacite (a chaque arc (i , j) ∈ ~E estassociee une capacite c(i , j) ≥ 0).

Remarque :s et t sont deux sommets particuliers de G .

Chapitre 8 : Flots dans les reseaux - Flot realisable 5/57

Flot realisable

Definition : flot realisableSoit R = (G = (V , ~E ), s, t, c) un reseau. Un flot f dans R est

une application f :→ N,Q+.Un flot f est realisable dans R si

1 contrainte de capacite0 ≤ f (i , j) ≤ c(i , j) ∀(i , j) ∈ ~E

2 contraintes de conservation de flot (Loi de Kirschoff)∑i | (i ,j)∈~E

f (i , j)−∑

k | (j ,k)∈~E

f (j , k) = 0 ∀j ∈ V \{s, t}

(quantite qui entre dans j = quantite qui sort de j)


Flot realisableExemple :

s

v1

v2

t

(5)

(6)

(4)

(7)

( ?)

5

5

2

3

7

capacite

flotx

(2)

Le flot est realisable.

contraintes de capacite Okcontraintes de conservationde flot Oken v1 : 5-2-3=0en v2 : 5+2-7=0


Valeur d’un flot

Definition : valeur d’un flotSoit R = (G = (V , ~E ), s, t, c) un reseau.

La valeur d’un flot f realisable entre s et t est la quantite de flotenvoyee de s a t. On la note F et

F =∑

i | (s,i)∈~E

f (s, i)−∑

j | (j ,s)∈~E

f (j , s) =

∑i | (i ,t)∈~E

f (i , t)−∑

j | (t,j)∈~E

f (t, j)

Exemple :Ici, la valeur du flot est de 10. (F = 5 + 5 = 3 + 7 = 10).


Arc sature

Definition : arc satureUn arc (i , j) est dit sature pour un flot f si f (i , j) = c(i , j).

Exemple :

s

v1

v2

t

(5)

(6)

(4)

(7)

( ?)

5

5

2

3

7

capacite

flotx

(2)

Ici, les arcs (s, 1), (1, 2) et (2, t) sont satures.Les arcs (s, 2) et (1, t) ne le sont pas.


Arc retourRemarque :Pour que la contrainte de conservation de flot soit verifiee en tout

sommet (y compris (s et t), on ajoute un arc artificiel (t, s) decapacite infinie et appele arc de retour.

s

v1

v2

t

(5)

(6)

(4)

(7)

5

5

2

3

7

(2)

F = 10(+∞)

Si aucun autrearc n’entre en s,la valeur F duflot f est alorsdonnee a f (t, s).


Le probleme du flot maximum

Probleme :Soit un reseau R = (G = (V , ~E ), s, t, c).Le probleme du flot maximum consiste a determinerun flot realisable entre s et t qui soit de valeurmaximum.

Chapitre 8 : Flots dans les reseaux - Le probleme du flot maximum 11/57

Le probleme du flot maximum : exempleExemple :On remarque que le flot donne dans le reseau precedent n’est pas

maximum. En effet, on peut trouver un flot de valeur 11.

s

v1

v2

t

(5)

(6)

(4)

(7)

(2)

5

76

1

4

11 11

Ce nouveau flot est maximum.En effet, on remarque qu’au mieux il peut rentre 11 unites de flotdans t a cause des capacites 4 et 7 sur les arcs entrants.


Plusieurs sources, plusieurs puits

Remarque :Le probleme du flot maximum peut etre generalise de la maniere

suivante :Supposons qu’il existe un ensemble de sommets sources et unensemble de puits.On desire determiner un flot max qui peut etre envoye de toutesles sources aux differents puits.Ce probleme peut etre ramene au probleme precedent en ajoutantune super-source s0 et un super-puits t0. On relie la super-source atoutes les sources avec des arcs de capacite infinie et on relie lesuper-puits aux differents puits avec des arcs de capacite infinie. Leprobleme se ramene alors a un probleme de flot max de s0 a t0.


Plusieurs sources, plusieurs puits

Exemple :sources : v1 et v2 et puits : v4 et v5

s0

v1

v2

v3

v4

v5

t0

1

(+∞)

(+∞)

(4)

(3)

(4)

(2)

(+∞)

(+∞)

(1)

(2)

(1)


Flot maximum et PL

Soient f (i , j) = flot transitant sur l’arc (i , j) ∀(i , j) ∈ ~EF = valeur du flot f

Le probleme du flot maximum entre s et t peut se formuler de lamaniere suivante :

Max F

s.c.∑

i | (i,j)∈~E

f (i , j)−∑

k | (j,k)∈~E

f (j , k) =

−F si j = s0 si j 6= s, tF si j = t

∀j ∈ V

0 ≤ f (i , j) ≤ c(i , j) ∀(i , j) ∈ ~E

Ce programme lineaire a |~E |+ 1 variableset 2|~E |+ |V | contraintes.


Chaınes augmentantes

Exemple :

s

v1

v2

t

(5)

(6)

(4)

(7)

(2)

Pour determiner un flot maximum dans ce reseau, on peutcommencer par envoyer du flot sur des chemins de s a t.

Chapitre 8 : Flots dans les reseaux - Chaınes augmentantes 16/57


→ Par exemple, on peut commencer par envoyer un flot de 2 sur lechemin (s, 1, 2, t).

s

v1

v2

t

(5)

(6)

(4)

(7)

(2)



→ Vu qu’il y a une reserve de capacite de 3 sur le chemin (s, 1, t),on peut envoyer 3 unites de flot.

s

v1

v2

t

(5)

(6)

(4)

(7)

(2)

2

22

22

0

0



→ Vu qu’il reste une reserve de 5 sur le chemin (s, 2, t), on peutenvoyer un flot de 5 sur ce chemin.

s

v1

v2

t

(5)

(6)

(4)

(7)

(2)5

5

2

25

3

0

Mais ce flot n’est pas maximum.


Chaınes augmentantesConsiderons la chaıne

s

v1

v2

t

(6)

(4)

(2)

5

2

3

On remarque que l’on peut :

augmenter le flot de 1 sur (s, 2),

diminuer le flot de 2 sur (1, 2),

augmenter le flot de 1 sur (1, t).



Donc en augmentant le flot de 1 sur les arcs (s, 2) et (1, t) et en lediminuant de 1 sur l’arc (1, 2) on aura le flot realisable suivant :

s

v1

v2

t

(5)

(6) (7)

(2)

5

2

3

10

5 710

(4)



Les contraintes de conservation de flot sont respectees.v1

v2

t

+1

-1s

v1

v2

+1

-1



Definition : chaıne augmentanteUne chaıne C entre s et t est dite augmentante par rapport a un

flot f = (f (i , j), (i , j) ∈ ~E ) realisable entre s et t si

f (i , j) < c(i , j) si (i , j) ∈ C+ ((i , j) ∈ ~E ) arc conforme)

f (i , j) > 0 si (i , j) ∈ C− ((j , i) ∈ ~E ) arc non conforme)

ou C+ est l’ensemble des arcs de C rencontres dans le bon sens etC− est l’ensemble des arcs de C rencontres dans le sens contraire.



Exemple :

s

v1

v2

t

(6)

(4)

(2)

arcs conformesarcs non conformes5 < 6, 2 > 0, 3 < 4La chaıne (s, 2, 1, t) est bien une chaıne augmentante.



Lemme :Soit f = (f (i , j), (i , j) ∈ ~E ) realisable entre s et t.

S’il existe une chaıne augmentante par rapport a f entre s ett,alors f n’est plus maximum.Preuve :

�


Procedure de marquage

Cette procedure permet, etant donne un flot realisable, dedeterminer si elle existe, une chaıne augmentante par rapport a f .Cette procedure est basee sur 2 operations de marquage dits :marquage direct et marquage indirect.

Chapitre 8 : Flots dans les reseaux - Algorithme de Ford et Fulkerson (1961) 26/57

Marquage direct

Marquage direct :Si pour un arc (i , j) on a

*

f (i, j) < c(i, j)i j

i marquej non marquef (i , j) < c(i , j)alorson marque jet on pose

δ(j) =min(δ(i), c(i , j)− f (i , j))δ(j) est la quantite max avec laquelle on peut augmenter le flot des a j .(δ(i) est une valeur associee a i , elle est initialisee a l’infini pour s.)


Marquage indirect

Marquage indirect :Si pour un arc (j , i) on a

*

f (j, i) > 0i j

i marquej non marquef (j , i) > 0alorson marque jet on pose

δ(j) =min(δ(i), f (j , i))


Algorithme de la chaıne augmentante

Supposons que l’on dispose d’un flot realisablef = (f (i , j), (i , j) ∈ ~E ) entre s et t.

Etape 1 : (initialisation)

Marquer s par (s,+).Poser δ(s) = +∞.

Etape 2 : Repeter les operations suivantes jusqu’a ce que tsoit marque ou qu’il ne soit plus possible de mar-quer.



Operation a)Si il existe un arc (i , j) tel que

i marquej non marquef (i , j) < c(i , j)

AlorsMarquer j par (i ,+)Poser δ(j) = min(δ(i), c(i , j)− f (i , j))



Operation b)Si il existe un arc (j , i) tel que

i marquej non marquef (j , i) > 0

AlorsMarquer j par (i ,−)Poser δ(j) = min(δ(i), f (j , i))



Etape 3 : Si t est marque Alorsune chaıne augmentante C entre s et t est

detectee et on pose ε = δ(t)Sinon

le flot f est maximum.


Algorithme de la chaıne augmentanteExemple :Considerons le reseau suivant ou le flot de depart est nul (donc

uniquement marquage direct possible).

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)


Algorithme de Ford et FulkersonOn suppose que l’on dispose d’un flot initial f = (f (i , j), (i , j) ∈ ~E )entre s et t (on peut prendre f = 0).

Etape 1 : Appliquer l’algorithme de la chaıne augmentante af .Si t est marque,

STOP f est optimal.Sinon

une chaıne augmentante C est detectee, aller al’etape 2.

Etape 2 : Changer le flot f comme suit :

f (i , j) =

f (i , j) si (i , j) 6∈ Cf (i , j) + ε si (i , j) ∈ C+

f (i , j)− ε si (i , j) ∈ C−Aller a l’etape 1.


Algorithme de Ford et Fulkerson

Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)4

1 0

3

45

0

2 0

2

11 2

7 99



Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)4

1 0

3

4

2

11

711

2

0

7

2

4

11



Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)4

1 0

3

4

2

11

77

2

13

2

4

6

13



Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)4

1 0

3

4

1

7

4

6

14

3

1 3

0

8 14


Coupe

Definition : coupeEtant donne un graphe G =(V , ~E ) et un sous-ensemble S desommets de V , on appelle coupeassociee a S , et on la note δ(S),l’ensemble des arcs (i , j) tels quei ∈ S et j ∈ V \S .

Chapitre 8 : Flots dans les reseaux - La coupe minimum 39/57

Coupe

Exemple :

1 2

5

4

3

δ({1, 3, 4}) = {(1, 2), (1, 5), (3, 2), (4, 5)}


Coupe

Definition : separeEtant donnes deux sommets s et t de G et une coupe δ(S), on dit

que δ(S) separe s et t si s ∈ S et t ∈ V \S .Exemple :

1 2

5

4

3

La coupe ci-contre separe 1 et5.Elle separe aussi 3 et 2.


Capacite d’une coupe

Definition : capacite d’une coupeSi c = (c(i , j), (i , j) ∈ ~E ) est un systeme de capacites associe aux

arcs du graphe G = (V , ~E ) et si δ(S) est une coupe du graphealors la capacite de δ(S) est definie par

C (δ(S)) =∑

(i ,j)∈δ(S)

c(i , j).


Flots et coupes

Theoreme :Soit un reseau R = (G = (V , ~E ), s, t, c).

Si f = (f (i , j), (i , j) ∈ ~E ) est un flot realisable entre s et t devaleur F et si δ(S) est une coupe qui separe s et t alors

F ≤ C (δ(S)).

Preuve :

�Chapitre 8 : Flots dans les reseaux - La coupe minimum 43/57

Th du flot max - coupe min

Theoreme : Th du flot max - coupe minLa valeur maximum d’un flot realisable entre s et t est egale

a la capacite minimum d’une coupe separant s et t.Preuve :

�


Th du flot max - coupe min

Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)(4)

(4)

(5)

(1)

(1) (6)

(9)

(1)1 0

3

4

1

14

3

7

4

0

3

4

1

6

148

Remarque :Tous les arcs appartenant a la coupe sont satures et la valeur du

flot sur ces arcs est bien de 3+4+1+6=14.


Flots entiers

Remarque :Si les capacites sont entieres alors le flot max a des valeurs

entieres.


Graphe d’ecart

Definition : graphe d’ecartSoit R = (G = (V , ~E ), s, t, c) un reseau. Soit f un flot sur R.

Gf = (V , ~Ef ) est le graphe d’ecart de f avec pour (i , j) ∈ ~E :

f (i , j) < c(i , j) ⇒ (i , j) ∈ ~Ef (arc conforme)

f (i , j) > 0 ⇒ (j , i) ∈ ~Ef (arc non conforme)

Chapitre 8 : Flots dans les reseaux - Implementation et complexite de l’algorithme de Ford et Fulkerson 47/57

Graphe d’ecart

Exemple :

1 3 5

2

4 6

7

(5)

(1)

(3)

(4)(7)

(2)

(4)

(5)

(1)

(1) (6)

(9)

(1)4

4

13

(4)2

7

1 0

3

4

1

2 1

6

7 13

2


Graphe d’ecart

Exemple :arcs conformes

arcs non conformes

1 3 5

2

4 6

7

4

(5)


Graphe d’ecart


arcs non conformes

1 3 5

2

4 6

7

7

(7)


Graphe d’ecart


arcs non conformes

1 3 5

2

4 6

7

0(1)


Graphe d’ecart

Exemple :

arcs non conformes

arcs conformes

1 3 5

2

4 6

7


Graphe d’ecartRemarque :La recherche d’une chaıne augmentante se ramene a un parcours

en profondeur dans le graphe d’ecart a partir s.Exemple :

arcs non conformes

arcs conformes

1 3 5

2

4 6

7


Graphe d’ecart

Remarque :On calcule ensuite les capacites residuelles sur la chaıne de s a t.

Exemple :

arcs non conformes

arcs conformes

2 2 3

1

2

1 3 5

2

4 6

7

ε = 1


Complexite

1 Complexite d’une iteration : O(m)

recherche d’une chaıne augmentanteparcours en profondeur :O(m)2m arcs au pluscalcul de la capacite residuelle pour la chaınetrouver le minimum d’au plus n − 1 capacites residuellesO(n)calcul du nouveau flot : O(n)construction du nouveau graphe d’ecart :au max 2× (n − 1) arcs qui changent : O(n)

2 Nombre max d’iterations de Ford / Fulkerson


Complexite

1 Complexite d’une iteration : O(m)

2 Nombre max d’iterations de Ford / Fulkersonhypotheses : c ∈ N et le flot de depart est entier.Les capacites residuelles sont entieres.⇒ la suite des flots est entiere.⇒ la valeur du flot augmente au moins de 1 a chaqueiteration.⇒ au plus F ∗ iterations avec F ∗=valeur du flot max.F ∗ ≤

∑j c(s, j) ≤ (n − 1)C avec C = max

(i ,j)∈~Ec(i , j)

donc au pire, (n − 1)C iterations.

Complexite dans le pire des cas de Ford / Fulkerson : O(n.m.C )


Ameliorations de Ford et Fulkerson

Idee 1 : Choisir une chaıne augmentante de capacite residuellemaximum.→ pas de garantie que les augmentations suivantes→ ce n’est plus un parcours mais la recherche d’un chemin dedebit maximum

Idee 2 : Choisir une chaıne augmentante la plus courte possible entermes de nombre d’arcs.→ parcours en largeur


Documents

Chapitre 8 : Flots dans les r eseaux - LIPN – …lipn.univ-paris13.fr/~borne/Docs/Graphes_chap8_Flots...Plan 1 Flot r ealisable 2 Le probl eme du ot maximum Exemple Plusieurs sources,