Curs 9Conectivitate: algoritmul lui Dijkstra.

Retele de transport: algoritmi de flux maxim

Curs 9

Continutul cursului

1 Problema celor mai usoare cai de la un nod sursa ıntr-undigraf ponderat

Algoritmul lui Dijkstra

2 Retele de transport si fluxuri

Flux maximRetele reziduale, drumuri de crestereAlgoritmul Ford-FulkersonAplicatii

Curs 9

Drumuri minime de la un nod sursa precizat

Se da un digraf ponderat simplu G = (V ,E ) cuw : E 7→ R+ si un nod sursa s ∈ V

Sa se determine pentru fiecare nod x ∈ V accesibil din s, o caleρ : s x care este cea mea usoara de la s la x ,precum si greutatea ei w(ρ)

Reamintim ca:

I Greutatea unui arc (u, v) ∈ E este w(u, v) > 0

I Greutatea unei cai [x1, x2, . . . , xn] de la x1 la xn este sumagreutatilor arcelor sale:

w([x1, x2, . . . , xn]) := w((x1, x2))+w((x2, x3))+. . .+w((xn−1, xn))

I O cale s x de la nodul s la x este cea mai usoara daca nuexista alta cale de la s la x cu greutate mai mica.

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat

G = (V ,E ) cu nodul sursa s:s

x

u

y

v10

5

2

9

1

2 3 4 67

Cu algoritmul lui Warshall putem calcula toate caile cele mai usoare

dintre oricare doua noduri. Presupunem ca nodurile sunt enumerate ın

ordinea 1:s, 2:u, 3:v , 4:x , 5:y

Mai ıntai scriem matricea WP [0] = WP [] care contine caile directe

dintre oricare doua noduri:

WP [] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 •∞ [y, v ]6 •∞ [y ]0

)Apoi calculam matricea WP [1] = WP [s] a cailor care pot trece doar

prin nodul intermediar 1:s

WP [s] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat

G = (V ,E ) cu nodul sursa s:s

x

u

y

v10

5

2

9

1

2 3 4 67

Cu algoritmul lui Warshall putem calcula toate caile cele mai usoare

dintre oricare doua noduri. Presupunem ca nodurile sunt enumerate ın

ordinea 1:s, 2:u, 3:v , 4:x , 5:y

Mai ıntai scriem matricea WP [0] = WP [] care contine caile directe

dintre oricare doua noduri:

WP [] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 •∞ [y, v ]6 •∞ [y ]0

)

Apoi calculam matricea WP [1] = WP [s] a cailor care pot trece doar

prin nodul intermediar 1:s

WP [s] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat

G = (V ,E ) cu nodul sursa s:s

x

u

y

v10

5

2

9

1

2 3 4 67

Cu algoritmul lui Warshall putem calcula toate caile cele mai usoare

dintre oricare doua noduri. Presupunem ca nodurile sunt enumerate ın

ordinea 1:s, 2:u, 3:v , 4:x , 5:y

Mai ıntai scriem matricea WP [0] = WP [] care contine caile directe

dintre oricare doua noduri:

WP [] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 •∞ [y, v ]6 •∞ [y ]0

)Apoi calculam matricea WP [1] = WP [s] a cailor care pot trece doar

prin nodul intermediar 1:s

WP [s] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [2] = WP [s,u] a cailor care pot trece

doar prin primele doua noduri intermediare:

WP [s,u] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s] =

([s]0 [s, u]10 •∞ [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, v ]9 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [2] = WP [s,u] a cailor care pot trece

doar prin primele doua noduri intermediare:

WP [s,u] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [3] = WP [s,u,v ] a cailor care pot trece

doar prin primele trei noduri intermediare:

WP [s,u,v ] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 [s, u, v, y ]15•∞ [u]0 [u, v ]1 [u, x]2 [u, v, y ]5•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 •∞•∞ [u]0 [u, v ]1 [u, x]2 •∞•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [3] = WP [s,u,v ] a cailor care pot trece

doar prin primele trei noduri intermediare:

WP [s,u,v ] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 [s, u, v, y ]15•∞ [u]0 [u, v ]1 [u, x]2 [u, v, y ]5•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u,v ] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 [s, u, v, y ]15•∞ [u]0 [u, v ]1 [u, x]2 [u, v, y ]5•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [4] = WP [s,u,v ,x] a cailor care pot trece

doar prin primele 4 noduri intermediare:

WP [s,u,v ,x] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7•∞ [u]0 [u, v ]1 [u, x]2 [u, x, y ]4•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u,v ] =

([s]0 [s, u]10 [s, u, v ]11 [s, x]5 [s, u, v, y ]15•∞ [u]0 [u, v ]1 [u, x]2 [u, v, y ]5•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, u]17 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [4] = WP [s,u,v ,x] a cailor care pot trece

doar prin primele 4 noduri intermediare:

WP [s,u,v ,x] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7•∞ [u]0 [u, v ]1 [u, x]2 [u, x, y ]4•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u,v ,x] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7•∞ [u]0 [u, v ]1 [u, x]2 [u, x, y ]4•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [5] = WP [s,u,v ,x,y ] a cailor care pot trece

prin oricare din cele 5 noduri:

WP [s,u,v ,x ,y ] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7

[u, x, y, s]11 [u]0 [u, v ]1 [u, x]2 [u, x, y ]4[v, y, s]11 [v, y, s, x, u]19 [v ]0 [v, y, s, x]16 [v, y ]4[x, y, s]9 [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatExemplu ilustrat (continuare)

s

x

u

y

v10

5

2

9

1

2 3 4 67

s:1, u:2, v :3, x :4, y :5

WP [s,u,v ,x] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7•∞ [u]0 [u, v ]1 [u, x]2 [u, x, y ]4•∞ •∞ [v ]0 •∞ [v, y ]4•∞ [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Apoi calculam matricea WP [5] = WP [s,u,v ,x,y ] a cailor care pot trece

prin oricare din cele 5 noduri:

WP [s,u,v ,x ,y ] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7

[u, x, y, s]11 [u]0 [u, v ]1 [u, x]2 [u, x, y ]4[v, y, s]11 [v, y, s, x, u]19 [v ]0 [v, y, s, x]16 [v, y ]4[x, y, s]9 [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

Curs 9

Drumuri minime de la un nod sursa precizatObservatii

WP [s,u,v ,x ,y ] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7

[u, x, y, s]11 [u]0 [u, v ]1 [u, x]2 [u, x, y ]4[v, y, s]11 [v, y, s, x, u]19 [v ]0 [v, y, s, x]16 [v, y ]4[x, y, s]9 [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

1 Algoritmul lui Warshall calculeaza matricea WP [s,u,v ,x ,y ] intimp O(|V |3)

2 Ne intereseza doar caile cele mai usoare de la s la celelaltenoduri – prima linie a matricii WP [s,u,v ,x ,y ].

Algoritmul lui Warshall calculeaza prea mult!

Intrebare. Putem calcula mai eficient doar caile care neintereseaza?Raspuns. Da: algoritmul lui Dijkstra

Curs 9

Drumuri minime de la un nod sursa precizatObservatii

WP [s,u,v ,x ,y ] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7

[u, x, y, s]11 [u]0 [u, v ]1 [u, x]2 [u, x, y ]4[v, y, s]11 [v, y, s, x, u]19 [v ]0 [v, y, s, x]16 [v, y ]4[x, y, s]9 [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

1 Algoritmul lui Warshall calculeaza matricea WP [s,u,v ,x ,y ] intimp O(|V |3)

2 Ne intereseza doar caile cele mai usoare de la s la celelaltenoduri – prima linie a matricii WP [s,u,v ,x ,y ].

Algoritmul lui Warshall calculeaza prea mult!Intrebare. Putem calcula mai eficient doar caile care neintereseaza?

Raspuns. Da: algoritmul lui Dijkstra

Curs 9

Drumuri minime de la un nod sursa precizatObservatii

WP [s,u,v ,x ,y ] =

([s]0 [s, x, u]8 [s, x, u, v ]9 [s, x]5 [s, x, y ]7

[u, x, y, s]11 [u]0 [u, v ]1 [u, x]2 [u, x, y ]4[v, y, s]11 [v, y, s, x, u]19 [v ]0 [v, y, s, x]16 [v, y ]4[x, y, s]9 [x, u]3 [x, u, v ]4 [x]0 [x, y ]2

[y, s]7 [y, s, x, u]15 [y, v ]6 [y, s, x]12 [y ]0

)

1 Algoritmul lui Warshall calculeaza matricea WP [s,u,v ,x ,y ] intimp O(|V |3)

2 Ne intereseza doar caile cele mai usoare de la s la celelaltenoduri – prima linie a matricii WP [s,u,v ,x ,y ].

Algoritmul lui Warshall calculeaza prea mult!Intrebare. Putem calcula mai eficient doar caile care neintereseaza?Raspuns. Da: algoritmul lui Dijkstra

Curs 9

Algoritmul lui DijkstraDescriere informala

Propus de E. Dijkstra ın 1956 pentru a rezolva problema anterioara

1 Se atribuie

o greutate tentativa d(x) pentru calea cea mai usoara la fiecare nod x .

un nod precedent π(x) fiecarui nod x pe calea cea mai usoara de la s la x .

Initial avem d(x) =

{0 daca x = s,∞ daca x 6= s

π(x) =

{nedef daca x = ss daca x 6= s

unde nedef este o valoare speciala care indica inexistenta unui nod parinte.

2 Creaza o multime Q de noduri nevizitate. Initial, Q := V , si tine evidenta unuinod curent crt.

3 Alege crt :=nod din Q cu d(crt) = min{d(x) | x ∈ Q}, si elimina crt din Q.

4 Pentru fiecare vecin x ∈ Q al lui crt actualizeaza valorile tenative ale lui d(x) siπ(x) astfel:

Daca d(crt) + w((crt, x)) < d(x) atuncid(x) := d(crt) + w((crt, x)) si π(x) := crt.

Acest pas de actualizare se numeste pas de relaxare a arcului (crt, x) ∈ E .

5 Daca Q = ∅ atunci stop, altfel goto 3.

Curs 9

Algoritmul lui DijkstraPseudocod pentru operatiile auxiliare

I Initializare

InitOSursa(G , s)pentru fiecare v ∈ V

d(v) :=∞π(v) := s

d(s) := 0π(s) := null

I Pasul de relaxare a unui arc (u, v)

Relaxeaza(u, v)Daca d(v) > d(u) + w((u, v))

d(v) := d(u) + v((u, v))π(v) := π(u)

s

u

v

d(u)

d(v)

w((u, v))

Curs 9

Algoritmul lui DijkstraPseudocod

Dijkstra(G ,w , s)1 InitOSursa(G , s)2 Q := V3 while Q 6= ∅4 u :=ExtractMin(Q)

5 for fiecare vecin v al lui u pentru care v 6∈ Q6 Relaxeaza(u, v)

Complexitate temporala:

B Algoritmul original: O(|V |2)

B Algoritmul ımbunatatit cu o coada cu prioritate minima:O(|E |+ |V | · log |V |)

Curs 9

Algoritmul lui DijkstraExemplu ilustrat: prima bucla while

Conventie: Nodurile nemarcate ınca (cele din Q) sunt albe;celelalte sunt cenusii

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :∞π:s

d :∞π:s

d :∞π:s

d :∞π:s

Configuratia produsa de InitializeSingleSource(G , s):

Q = {s, x , y , u, v}Se selecteaza s = ExtractMin(Q)

Se relaxeaza toate arcele care pleaca din s spre noduri nevizitateınca:

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :∞π:s

d :∞π:s

d :5π:s

d :∞π:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :10π:s

d :∞π:s

d :5π:s

d :∞π:s

Curs 9

Algoritmul lui DijkstraExemplu ilustrat: a doua bucla while

Se selecteaza si marcheaza x , si se relaxeaza toate arcele carepleaca din x spre noduri nemarcate:

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :∞π:s

d :5π:s

d :∞π:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :14π:x

d :5π:s

d :∞π:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :14π:x

d :5π:s

d :7π:x

Curs 9

Algoritmul lui DijkstraExemplu ilustrat: a treia bucla while

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :14π:x

d :5π:s

d :7π:x

Se selecteaza si marcheaza y , si se relaxeaza toate arcele carepleaca din y spre noduri nemarcate:

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :13π:y

d :5π:s

d :7π:x

Curs 9

Algoritmul lui DijkstraExemplu ilustrat: a patra bucla while

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :13π:y

d :5π:s

d :7π:x

Se selecteaza si marcheaza u, si se relaxeaza toate arcele carepleaca din u spre noduri nemarcate:

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :9π:u

d :5π:s

d :7π:x

Curs 9

Algoritmul lui DijkstraExemplu ilustrat: a cincea bucla while

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

π:nedef

d :8π:x

d :9π:u

d :5π:s

d :7π:x

d(s) = 0

d(x) = 5

d(u) = 8

d(y) = 7

d(v) = 9

π(s) = nedef

π(x) = s

π(u) = x

π(y) = x

π(v) = u

Se selecteaza si marcheaza v

N-a mai ramas de relaxat nici un arc ⇒ algoritmul se opreste.

Din valorile lui π si d putem extrage caile cele mai usoare:

I la s: [s] cu greutatea w([s]) = d(s) = 0

I la x : [s, x ] cu greutatea w([s, x ]) = d(x) = 5

I la u: [s, x , u] cu greutatea w([s, x , u]) = d(u) = 8

I la y : [s, x , y ] cu greutatea w([s, x , y ]) = d(y) = 7

I la v : [s.x , u, v ] cu greutatea w([s, x , u, v ]) = d(v) = 9

Curs 9

Arborele celor mai usoare cai de la un nod sursa

Functia π calculata de algoritmul lui Dijkstra determina un arboreGπ cu radacina s, ın care fiecare nod x 6= s are parintele π(x).

Exemplu (Arborele Gπ pentru digraful simplu ponderat G ilustrat)

s

x

u y

v

5

23

1

Observatie

Orice ramura a lui Gπ de la nodul sursa s la un nod x este o calecea mai usoara de la s la x .

Curs 9

Referinte

1 T. H. Cormen, C. E. Leiserson, R. L. Rivest. Sectiunea 25.2din Introduction to Algorithms. MIT Press, 2000.

2 O implementare ın C++ a algoritmului lui Dijkstra poate fidescarcata de pe pagina web a cursului (click aici)

Curs 9

Retele de transport si fluxuriDefinitii intuitive (neformale)

Retea de transport: Graf orientat ın care muchiile modeleazafluxuri de materiale ıntre noduri (litri de lichid,amperi de electricitate, etc.)

Fiecare muchie are o capacitate maxima.Se doreste stabilirea unui flux de resurse de la unnod sursa (producatorul) la un nod destinatie(consumatorul).

Flux ≈ debitul de deplasare a resurselor de-a lungulmuchiilor.

Problema debitului maxim: Care este debitul maxim al unui flux deresurse de la sursa la destinatie, fara sa se violeze nici oconstrangere de capacitate maxima ale muchiilor?

Curs 9

Retele de transportModel matematic

Definitie (Retea de transport)

Un graf orientat G = (V ,E ) ın care fiecare muchie (u, v) ∈ E areo capacitate c(u, v) ≥ 0 si doua noduri speciale:

o sursa s si

o destinatie t.

Daca (u, v) 6∈ E , se considera ca c(u, v) = 0.Scriem u v pentru a indica existenta unei cai de la u la v , sipresupunem ca fiecare nod v ∈ G este pe o cale de la s la t, adicaexista o cale s v t.

Observatie

O retea de transport este un graf conex, deci |E | ≥ |V | − 1.

Curs 9

Fluxuri

Definitie

Un flux ın o retea de transport G este o functie f : V × V → Rcare satisface 3 conditii:

Restrictie de capacitate: Pentru toti u, v ∈ V , f (u, v) ≤ c(u, v).

Antisimetrie: pentru toti u, v ∈ V , f (u, v) = −f (v , u).

Conservarea fluxului: Pentru toti u ∈ V − {s, t},∑v∈V

f (u, v) = 0.

f (u, v) se numeste fluxul net de la nodul u la v . Valoarea fluxuluif este |f | =

∑v∈V f (s, v), adica, fluxul total de retea care pleaca

din sursa.

Problema fluxului maxim

Se da o retea de transport G cu sursa s si destinatia t,

Sa se gaseasca un flux cu valoare maxima de la s la t.

Curs 9

Retele de transport si fluxuriNotiuni auxiliare

Fluxul pozitiv de retea care intra ıntr-un nod v este∑u∈V

f (u,v)>0

f (u, v)

Fluxul pozitiv de retea care pleaca dintr-un nod v este∑u∈V

f (v ,u)>0

f (v , u)

⇒ Din conservarea fluxului rezulta ca pentru orice nod v 6∈ {s, t}:fluxul pozitiv care intra ın v = fluxul pozitiv care pleaca din v .

Curs 9

Exemplu de retea de transport

s

v1

v2

v3

v4

t16

13

10 4

12

14

7

20

4

9

(a)

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

(b)

(a) Retea de transport G = (V ,E ) cu muchiile etichetate cucapacitatile lor. Sursa este s, destinatia este t.

(b) Un flux f ın reteaua de transport G cu valoarea |f | = 19.Sunt indicate doar fluxurile pozitive. Daca f (u, v) > 0,muchia (u, v) este etichetata cu f (u, v)/c(u, v). (Notatia cu’/’ separa fluxul de capacitate; nu reprezinta ımpartire.) Dacaf (u, v) ≤ 0, muchia (u, v) este etichetata doar cu capacitateaei.

Curs 9

Retele de transportStergerea tuturor fluxurilor negative de retea – regula de anulare

Daca v1 ≥ v2 > 0 atunci

x y x y

v1/c1

v2/c2

(v1 − v2)/c1

c2

anulare

Doar fluxurile pozitive de retea reprezinta transporturi ce auloc.

Aplicatii ale regulii de anulare

elimina fluxurile negative de retea.nu violeaza cele 3 restrictii ale retelelor de transport:

1 constrangerea de capacitate2 antisimetria3 conservarea fluxului

Curs 9

Surse si destinatii multiple

O problema de debit maxim poate avea surse multiples1, . . . , sm si destinatii multiple t1, . . . , tn.

O astfel de problema poate fi redusa la o problema echivalentacu o singura sursa si o singura destinatie:

adauga o supersursa s si o superdestinatie tadauga muchii orientate (s, si ) cu c(s, si ) =∞ pentru i = 1..madauga muchii orientate (tj , t) cu c(tj , t) =∞ pentru j = 1..n

Exemplu

s1

s2

s3

s4

s5

s1

s2

s3

s4

t1

t2

t3

10

12

5

8

14

7

11

2

3

15

6

20

13

18

Curs 9

Surse si destinatii multiple

O problema de debit maxim poate avea surse multiples1, . . . , sm si destinatii multiple t1, . . . , tn.

O astfel de problema poate fi redusa la o problema echivalentacu o singura sursa si o singura destinatie:

adauga o supersursa s si o superdestinatie tadauga muchii orientate (s, si ) cu c(s, si ) =∞ pentru i = 1..madauga muchii orientate (tj , t) cu c(tj , t) =∞ pentru j = 1..n

Exemplu

s1

s2

s3

s4

s5

s1

s2

s3

s4

t1

t2

t3

10

12

5

8

14

7

11

2

3

15

6

20

13

18

s

s1

s2

s3

s4

s5

s1

s2

s3

s4

t1

t2

t3

t

∞∞∞∞∞

∞

∞

∞

10

12

5

8

14

7

11

2

3

15

6

20

13

18

Curs 9

Operatii cu fluxuriConventii de notatie

Se presupun date:

o retea de transport G = (V ,E )o functie f de la V × V la Rmultimile de noduri X ,Y (adica, X ⊆ V , Y ⊆ V )nodul u ∈ V .

Atunci

f (X ,Y ) reprezinta suma∑x∈X

∑y∈Y

f (x , y).

f (u,X ) reprezinta suma∑x∈X

f (u, x).

f (Y , u) reprezinta suma∑y∈Y

f (y , u).

X − u reprezinta multimea X − {u}.

Remarca. Daca f este un flux pentru G = (V ,E ) atuncif (u,V ) = 0 pentru toti u ∈ V − {s, t}. Acest fapt rezulta dinconservarea fluxului ⇒ f (V − {s, t},V ) = 0.

Curs 9

Proprietati ale retelelor de transport

Lema

Fie G = (V ,E ) o retea de transport si f un flux ın G . Dacax ,Y ,Z ⊆ V atunci

f (X ,X ) = 0

f (X ,Y ) = −f (Y ,X )

Daca X ∩ Y = ∅ atunci

I f (X ∪ Y ,Z ) = f (X ,Z ) + f (Y ,Z ), siI f (Z ,X ∪ Y ) = f (Z ,X ) + f (Z ,Y )

Se observa ca:

|f | = f (s,V ) cf. definitiei

= f (V ,V )− f (V − s,V ) cf. lemei precedente

= f (V ,V − s) cf. lemei precedente

= f (V , t) + f (V ,V − {s, t}) cf. lemei precedente

= f (V , t) cf. conservarii fluxului

Curs 9

Operatii cu fluxuri

Definitie

Daca f1, f2 sunt fluxuri ın o retea de transport G iar α ∈ R, atunci

suma fluxurilor f1 si f2 este functia f1 + f2 de la V × V la Rdefinita de

(f1 + f2)(u, v) := f1(u, v) + f2(u, v) pentru toti u, v ∈ V .

produsul scalar αf1 este fluxul definit de functia de la V × Vla R astfel ıncat

(α f1)(u, v) := α f1(u, v) pentru toti u, v ∈ V .

Curs 9

Operatii cu fluxuriExemple

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

(a) G si f1

s

v1

v2

v3

v4

t1/16

6/13

10 1/4

2/12

9/14

7/7

5/20

2/4

4/9

(b) G si f2

s

v1

v2

v3

v4

t12/16

14/13

10 1/4

14/12

20/14

7/7

20/20

6/4

4/9

(c) G si f1 + f2

s

v1

v2

v3

v4

t.5/16

3/13

5 .5/4

1/12

4.5/14

3.5/7

2.5/20

1/4

2/9

(d) G si α f2 cand α = 12

Curs 9

Operatii cu fluxuriExemple

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

(a) G si f1

s

v1

v2

v3

v4

t1/16

6/13

10 1/4

2/12

9/14

7/7

5/20

2/4

4/9

(b) G si f2

s

v1

v2

v3

v4

t12/16

14/13

10 1/4

14/12

20/14

7/7

20/20

6/4

4/9

(c) G si f1 + f2

s

v1

v2

v3

v4

t.5/16

3/13

5 .5/4

1/12

4.5/14

3.5/7

2.5/20

1/4

2/9

(d) G si α f2 cand α = 12

Curs 9

Operatii cu fluxuriExemple

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

(a) G si f1

s

v1

v2

v3

v4

t1/16

6/13

10 1/4

2/12

9/14

7/7

5/20

2/4

4/9

(b) G si f2

s

v1

v2

v3

v4

t12/16

14/13

10 1/4

14/12

20/14

7/7

20/20

6/4

4/9

(c) G si f1 + f2

s

v1

v2

v3

v4

t.5/16

3/13

5 .5/4

1/12

4.5/14

3.5/7

2.5/20

1/4

2/9

(d) G si α f2 cand α = 12

Curs 9

Operatii cu fluxuriIntrebari

Un flux trebiue sa satisfaca 3 constrangeri: restrictia de capacitate,antisimetria si conservarea fluxului.

1 Care proprietati nu sunt pastrate de sumele de flux?

2 Care proprietati nu sunt pastrate de produsul scalar al fluxului?

3 Sa se arate ca daca f1, f2 sunt fluxuri si 0 ≤ α ≤ 1, atunciα f1 + (1− α) f2 este flux.

Curs 9

Retele reziduale

Ipoteze: G = (V ,E ): retea de transport; f : flux ın G .

capacitatea reziduala a unei muchii (u, v) estecf (u, v) := c(u, v)− f (u, v).

retea reziduala a lui G indusa de f este reteaua de transportGf = (V ,Ef ) unde Ef = {(u, v) ∈ V × V | cf (u, v) > 0}, iarcapacitatea fiecarei muchii (u, v) este cf (u, v).

Exemplu

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

(a) G si f

s

v1

v2

v3

v4

t

5

11

5

8

11 3

12

11

3

7

5

15

4

5

4(b) Gf

Remarca. In general, |Ef | ≤ 2 |E |.Curs 9

Fluxuri ın retele rezidualeProprietati

Fie G o retea de transport, f un flux ın G , si reteaua reziduala Gf . Daca

f ′ este un flux ın Gf atunci f + f ′ este flux ın G cu valoarea

|f + f ′| = |f |+ |f ′|.

Demonstratie.

Antisimetria are loc deoarece (f + f ′)(u, v) = f (u, v) + f ′(u, v) =−f (v , u)− f ′(v , u) = −(f (v , u) + f ′(v , u)) = −(f + f ′)(v , u).

Pentru constrangerile de capacitate se observa caf ′(u, v) ≤ cf (u, v) pentru toti u, v ∈ V , deci (f + f ′)(u, v) =f (u, v) + f ′(u, v) ≤ f (u, v) + (c(u, v)− f (u, v)) = c(u, v).

Pentru conservarea fluxului observam ca∑v∈V

(f + f ′)(u, v) =∑v∈V

(f (u, v) + f ′(u, v))

=∑v∈V

f (u, v) +∑v∈V

f ′(u, v) = 0 + 0 = 0.

In final avem ca|f + f ′| =

∑v∈V

(f + f ′)(s, v) =∑v∈V

(f (s, v) + f ′(s, v)) =∑v∈V

f (s, v) +∑v∈V

f ′(s, v) = |f | + |f ′|.

Curs 9

Drumuri de crestere

Un drum de crestere al unei retele de transport G si a unui flux feste o cale simpla de la s la t ın reteaua reziduala Gf .

Exemplu (Drum de crestere)

s

v1

v2

v3

v4

t

5

11

5

8

11 3

12

11

3

7

5

15

4

5

4

Observatii.

Fiecare muchie (u, v) a unui drum de crestere admite un fluxnet pozitiv suplimentar fara ca sa violeze capacitatea muchiei.

In acest exemplu am fi putut trimite cel putin 4 unitati ın plusde la s la t de-a lungul drumului de crestere marcat, fara aviola vreo restrictie de capacitate (Remarca: capacitateareziduala minima pe drumul de crestere marcat este 4).

Curs 9

Drumuri de crestere (continuare)

Capacitatea reziduala a unui drum de crestere p este data de

cf (p) := min{cf (u, v) | (u, v) este pe p}.

Lema

Fie G = (V ,E ) o retea de transport cu un flux f , p un drum decrestere ın Gf , si fp : V × V → R definit de

fp(u, v) :=

cf (p) daca (u, v) este pe p,−cf (p) daca (v , u) este pe p,

0 ın celelalte cazuri.Atunci fp este un flux ın Gf cu valoarea |fp| = cf (p) > 0.

Corolar

Fie G = (V ,E ) o retea de transport cu fluxul f , si p un drum decrestere ın Gf . Fie fp fluxul definit ca ın lema precedenta. Atuncif + fp este un flux ın G cu valoarea |f ′| = |f |+ |fp| > |f |.

Curs 9

Metoda Ford-Fulkerson

Produce un flux maxim pentru o retea de transport G :

Ford-Fulkerson-Method(G , s, t)1 initializeaza fluxul f cu 02 while exista un drum de crestere p3 creste fluxul f de-a lungul lui p4 return f

Metoda Ford-Fulkerson este corecta deoarece are locurmatorul rezultat:

Un flux este maxim daca si numai daca reteaua luireziduala nu contine drumuri de crestere.

. Vom demonstra acest lucru.

Notiuni auxiliare: taietura, capacitate a unei taieturi.

Curs 9

Metoda Ford-Fulkerson

Produce un flux maxim pentru o retea de transport G :

Ford-Fulkerson-Method(G , s, t)1 initializeaza fluxul f cu 02 while exista un drum de crestere p3 creste fluxul f de-a lungul lui p4 return f

Metoda Ford-Fulkerson este corecta deoarece are locurmatorul rezultat:

Un flux este maxim daca si numai daca reteaua luireziduala nu contine drumuri de crestere.

. Vom demonstra acest lucru.

Notiuni auxiliare: taietura, capacitate a unei taieturi.

Curs 9

Taieturi

Definitie

O taietura (S ,T ) a unei retele de transport G = (V ,E ) este opartitie a lui V ın S si T = V − S astfel ıncat s ∈ S si t ∈ T .Fluxul net de-a lungul taieturii (S ,T ) este f (S ,T ). Capacitateataieturii (S ,T ) este c(S ,T ).

Exemplu

s

v1

v2

v3

v4

t11/16

8/13

10 1/4

12/12

11/14

7/7

15/20

4/4

4/9

← S T →

S = {s, v1, v2}T = {v3, v4, t}

f (S ,T ) = f (v1, v3)+f (v2, v3)+f (v2, v4) = 12+(−4)+11 = 19c(S ,T ) = c(v1, v3) + c(v2, v4) = 12 + 14 = 26

Curs 9

Proprietati ale taieturilor

Lema

Fluxul net de-a lungul oricarei taieturi (S ,T ) este f (S ,T ) = |f |.

Corolar

Pentru orice flux f si orice taietura (S ,T ) avem |f | ≤ c(S ,T ).

Teorema (Flux maxim – taietura minima)

Daca f este un flux ın o retea de transport G = (V ,E ) cu sursa ssi destinatia t, atunci conditiile urmatoare sunt echivalente:

1 f este un flux maxim ın G .

2 Gf nu contine drumuri de crestere.

3 |f | = c(S ,T ) pentru o taietura (S ,T ) a lui G .

Curs 9

Teorema flux maxim – taietura minima

(1)⇒ (2) Prin contradictie: Presupunem ca f este flux maximın G si ca Gf are n drum de crestere p. Atunci f + fpar fi un flux G cu valoare strict mai mare decat |f |,contradictie.

(2)⇒ (3) Presupunem ca Gf nu are drum de crestere de la s lat. Fie S = {v ∈ V | exista un drum de la s la v ınGf } si T = V − S . Atunci (S ,T ) este taieturadeoarece s ∈ S si t 6∈ S . Pentru orice pereche denoduri (u, v) ∈ S × T avem v(u, v) = c(u, v)deoarece ın caz contrar (u, v) ∈ Ef si v ∈ S . Rezultaca |f | = f (S ,T ) = c(S ,T ).

(3)⇒ (1) Stim ca |f | ≤ c(S ,T ) pentru toate taieturile (S ,T )ale lui G . Din conditia |f | = c(S ,T ) rezulta ca feste flux maxim.

Curs 9

Algoritmul Ford-Fulkerson de baza

Ford-Fulkerson(G , s, t)1 for fiecare muchie (u, v) a lui G2 f (u, v) := 03 f (v , u) := 04 while ∃ drum p de la s la t ın Gf

5 cf := min{cf (u, v) | (u, v) este ın p}6 for fiecare muchie (u, v) ın p7 f (u, v) := f (u, v) + cf (p)8 f (v , u) := −f (u, v)

Curs 9

Algoritmul Ford-Fulkerson de bazaExemplu ilustrat: initial, |f | = 0

s

v1

v2

v3

v4

t16

13

10 4

12

14

7

20

4

9(a)

Retea reziduala Gf cudrum de crestere (linia 4)

s

v1

v2

v3

v4

t4/16

13

10 4

4/12

4/14

7

20

4/4

4/9

Flux net ce rezulta dinadaugarea lui fp la f

s

v1

v2

v3

v4

t12

4

13

10 4

8

4

10

4

7

20

4

5

4(b) s

v1

v2

v3

v4

t11/16

13

7/10 4

4/12

11/14

7/7

7/20

4/4

4/9

s

v1

v2

v3

v4

t5

11

13

3 11

8

4

3

11

7

13

7

4

5

4(c) . . . . . . . . .

Exercitiu: sa se deseneze grafurile pentru pasii ramasi ai algoritmului lui

Ford-Fulkerson.Curs 9

Algoritmul Ford-Fulkerson de bazaAnaliza complexitatii

Timpul de executie depinde de felul cum se calculeaza drumulde crestere p ın linia 4 a algoritmului.

Ipoteza: toate muchiile au numere ıntregi ca si capacitati(adica 0,1,2,. . . ).

Daca capacitatile sunt numere rationale, le putem ınlocui cunumere ıntregi facand o operatie de scalare corespunzatoare.

O implementare directa a algoritmului Ford-Fulkersondureaza O(E · |f ∗|) unde f ∗ este fluxul maxim gasit dealgoritm.

Motiv: bucla while din liniile 4-8 se executa de cel mult |f ∗|ori deoarece valoarea fluxului creste cu cel putin 1 de fiecaredata.

Curs 9

Algoritmul Ford-Fulkerson de bazaAnaliza complexitatii

Timpul de executie depinde de felul cum se calculeaza drumulde crestere p ın linia 4 a algoritmului.

Ipoteza: toate muchiile au numere ıntregi ca si capacitati(adica 0,1,2,. . . ).

Daca capacitatile sunt numere rationale, le putem ınlocui cunumere ıntregi facand o operatie de scalare corespunzatoare.

O implementare directa a algoritmului Ford-Fulkersondureaza O(E · |f ∗|) unde f ∗ este fluxul maxim gasit dealgoritm.

Motiv: bucla while din liniile 4-8 se executa de cel mult |f ∗|ori deoarece valoarea fluxului creste cu cel putin 1 de fiecaredata.

Curs 9

Algoritmul Ford-Fulkerson de bazaAnaliza complexitatii

Timpul de executie depinde de felul cum se calculeaza drumulde crestere p ın linia 4 a algoritmului.

Ipoteza: toate muchiile au numere ıntregi ca si capacitati(adica 0,1,2,. . . ).

Daca capacitatile sunt numere rationale, le putem ınlocui cunumere ıntregi facand o operatie de scalare corespunzatoare.

O implementare directa a algoritmului Ford-Fulkersondureaza O(E · |f ∗|) unde f ∗ este fluxul maxim gasit dealgoritm.

Motiv: bucla while din liniile 4-8 se executa de cel mult |f ∗|ori deoarece valoarea fluxului creste cu cel putin 1 de fiecaredata.

Curs 9

Algoritmul Ford-Fulkerson de bazaAnaliza complexitatii

Timpul de executie depinde de felul cum se calculeaza drumulde crestere p ın linia 4 a algoritmului.

Ipoteza: toate muchiile au numere ıntregi ca si capacitati(adica 0,1,2,. . . ).

Daca capacitatile sunt numere rationale, le putem ınlocui cunumere ıntregi facand o operatie de scalare corespunzatoare.

O implementare directa a algoritmului Ford-Fulkersondureaza O(E · |f ∗|) unde f ∗ este fluxul maxim gasit dealgoritm.

Motiv: bucla while din liniile 4-8 se executa de cel mult |f ∗|ori deoarece valoarea fluxului creste cu cel putin 1 de fiecaredata.

Curs 9

Analiza complexitatiiUn exemplu care dureaza Θ(E · |f ∗|)

s

u

v

t1000000

1000000

1

1000000

1000000

(a)

s

u

v

t

999999

1

1000000

1

1000000

999999

1

(b)

s

u

v

t

999999

1

999999

11

9999991

999999

1

(c)

Un flux maxim f ∗ ın reteaua de transport (a) are|f ∗| = 2000000. A alegere proasta de drum de crestere cucapacitatea 1 este marcata cu rosu.(b) si (c) ilustreaza retelele reziduale produse dupa crestereacu drumul de crestere marcat cu rosu.

Complexitatea algoritmului se ımbunatateste daca p ın linia 4se calculeaza folosind o cautare ın latime care garanteaza ca peste o cale cea mai scurta de la s la t ın reteaua reziduala, ıncare fiecare muchie are o distanta unitara (greutate) ⇒algoritmul Edmonds-Karp cu complexitatea O(|V | · |E |2).

Curs 9

Analiza complexitatiiUn exemplu care dureaza Θ(E · |f ∗|)

s

u

v

t1000000

1000000

1

1000000

1000000

(a)

s

u

v

t

999999

1

1000000

1

1000000

999999

1

(b)

s

u

v

t

999999

1

999999

11

9999991

999999

1

(c)

Un flux maxim f ∗ ın reteaua de transport (a) are|f ∗| = 2000000. A alegere proasta de drum de crestere cucapacitatea 1 este marcata cu rosu.(b) si (c) ilustreaza retelele reziduale produse dupa crestereacu drumul de crestere marcat cu rosu.Complexitatea algoritmului se ımbunatateste daca p ın linia 4se calculeaza folosind o cautare ın latime care garanteaza ca peste o cale cea mai scurta de la s la t ın reteaua reziduala, ıncare fiecare muchie are o distanta unitara (greutate) ⇒algoritmul Edmonds-Karp cu complexitatea O(|V | · |E |2).

Curs 9

Aplicatii si extensiiAplicatia 1: Cuplaje ın grafuri bipartite

Fie B = (V ,E ) un graf bipartit ıntre submultimile V1 si V2 ale luiV .

Definitie (cuplaj, cuplaj maxim)

Un cuplaj ın B este o multime de muchii C ⊆ E cu proprietatea caoricare 2 muchii din C nu au un capat comun. Cuplajul C estemaxim daca are un numar maxim de muchii.

Calculul unui cuplaj maxim ın B = (V1 ∪ V2,E ) se poate faceastfel:

1 Extindem B cu 2 noduri noi: s (sursa) si t (destinatie), apoicu arcuri cu capacitatea 1 de la s la toate nodurile din V1, side la toate nodurile din V2 la t. Toate muchiile lui G seorienteaza de la V1 la V2, cu capacitatea 1 ⇒ o retea detransport.

2 Se calculeaza un flux maxim de la s la t

Curs 9

Aplicatii si extensiiAplicatia 1: Cuplaje ın grafuri bipartite

Construirea unei retele de transport pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

1

1

11

1

1

1

1

1

s t

1

1

1

1

1

1

1

1

1

1

1/1

1/11/

1

1/1

1/1

1/1

1/1

1/1

Cuplaj maxim C = {(x2, y1), (x3, y2), (x4, y4), (x5, y3)}

Teorema

Fie G reteaua de transport construita pentru un graf bipartit

B = (V1 ∪ V2,E ) si f un flux maxim ın G . Atunci multimea muchiilor

(u, v) ale lui f cu u ∈ V1, v ∈ V2 si f (u, v) = 1 este un cuplaj maxim ın

B.

Curs 9

Aplicatii si extensiiAplicatia 1: Cuplaje ın grafuri bipartite

Construirea unei retele de transport pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

1

111

1

1

1

1

1

s t

1

1

1

1

1

1

1

1

1

1

1/1

1/11/

1

1/1

1/1

1/1

1/1

1/1

Cuplaj maxim C = {(x2, y1), (x3, y2), (x4, y4), (x5, y3)}

Teorema

Fie G reteaua de transport construita pentru un graf bipartit

B = (V1 ∪ V2,E ) si f un flux maxim ın G . Atunci multimea muchiilor

(u, v) ale lui f cu u ∈ V1, v ∈ V2 si f (u, v) = 1 este un cuplaj maxim ın

B.

Curs 9

Aplicatii si extensiiAplicatia 1: Cuplaje ın grafuri bipartite

Construirea unei retele de transport pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

1

111

1

1

1

1

1

s t

1

1

1

1

1

1

1

1

1

1

1/1

1/11/

1

1/1

1/1

1/1

1/1

1/1

Cuplaj maxim C = {(x2, y1), (x3, y2), (x4, y4), (x5, y3)}

Teorema

Fie G reteaua de transport construita pentru un graf bipartit

B = (V1 ∪ V2,E ) si f un flux maxim ın G . Atunci multimea muchiilor

(u, v) ale lui f cu u ∈ V1, v ∈ V2 si f (u, v) = 1 este un cuplaj maxim ın

B.

Curs 9

Aplicatii si extensiiAplicatia 1: Cuplaje ın grafuri bipartite

Construirea unei retele de transport pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

1

111

1

1

1

1

1

s t

1

1

1

1

1

1

1

1

1

1

1/1

1/11/

1

1/1

1/1

1/1

1/1

1/1

Cuplaj maxim C = {(x2, y1), (x3, y2), (x4, y4), (x5, y3)}

Teorema

Fie G reteaua de transport construita pentru un graf bipartit

B = (V1 ∪ V2,E ) si f un flux maxim ın G . Atunci multimea muchiilor

(u, v) ale lui f cu u ∈ V1, v ∈ V2 si f (u, v) = 1 este un cuplaj maxim ın

B.Curs 9

Aplicatii si extensiiAplicatia 2: Flux maxim de cost minim

Problema

G = (V ,E ): retea de transport ın care muchiile (u, v) au asociate,pe langa o capacitate, si un cost unitar cost(u, v) ≥ 0.Un flux maxim de cost minim ın G este un flux maxim f ın Gpentru care suma ∑

(u,v)∈E

f (u, v) · cost(u, v)

este minima.

Curs 9

Aplicatii si extensiiAplicatia 2: Flux maxim de cost minim

Solutie: Adaptare a algoritmului Edmonds-Karp

Se asociaza costuri la toate muchiile din retelele reziduale aleunui flux f :

muchia (u, v) are costul cost(u, v) daca c(u, v) > f (u, v) ınreteaua originalamuchia (u, v) are costul −cost(u, v) daca f (u, v) < 0 ınreteaua originala

In loc de drum cel mai scurt de la sursa s la destinatia t, secauta un drum p de la s la t cu cost minim ın reteauareziduala.

p poate fi gasit cu algoritmul lui Bellman-Ford.

Apoi, fluxul va fi incrementat pe drumul p cu valoareamaxima posibila (=minimul diferentelor dintre capacitate siflux pentru fiecare arc de pe drum).

Curs 9

Bibliografie

Capitolul 27 din

T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction toAlgorithms. MIT Press, 2000.

Curs 9