limbaje algoritmi

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

Se doreste pentru fiecare nod x V accesibil din s, o cea meausoara cale : s x , precum si greutatea ei w()

Exemplu

s

x

u

y

v10

5

2

9

1

2 3 4 67

[s] cu w([s]) = 0

[s, x] cu w([s, x]) = 5

[s, x , y ] cu w([s, x , y ]) = 7

[s, x , u] cu w([s, x , u]) = 8

[s, x , u, v ] cu w([s, x , u, v ]) = 9

Observatie

Problema poate fi rezolvata cu algoritmul lui Warshall:

Calculeaza cele mai usoare cai existente pentru orice perechede noduriAre complexitatea O(|V |3) si calculeaza prea mult

Exista un algoritm mai eficient, daca nodul sursa este fixat?

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 pi(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 pi(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) sipi(x) astfel:

Daca d(crt) + w((crt, x)) < d(x) atuncid(x) := d(crt) + w((crt, x)) si pi(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 InitializareInitOSursa(G , s)

pentru fiecare v Vd(v) :=pi(v) := s

d(s) := 0pi(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))pi(v) := pi(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 := S3 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

pi:nedef

d :pi:s

d :pi:s

d :pi:s

d :pi: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 nevizitatenca:

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

pi:nedef

d :pi:s

d :pi:s

d :5pi:s

d :pi:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

pi:nedef

d :10pi:s

d :pi:s

d :5pi:s

d :pi: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

pi:nedef

d :8pi:x

d :pi:s

d :5pi:s

d :pi:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

pi:nedef

d :8pi:x

d :14pi:x

d :5pi:s

d :pi:s

s

x

u

y

v

7

10

5

2

9

1

2 3 4 6d :0

pi:nedef

d :8pi:x

d :14pi:x

d :5pi:s

d :7pi: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

pi:nedef

d :8pi:x

d :14pi:x

d :5pi:s

d :7pi: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

pi:nedef

d :8pi:x

d :13pi:y

d :5pi:s

d :7pi: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

pi:nedef

d :8pi:x

d :13pi:y

d :5pi:s

d :7pi: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

pi:nedef

d :8pi:x

d :9pi:u

d :5pi:s

d :7pi: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

pi:nedef

d :8pi:x

d :9pi:u

d :5pi:s

d :7pi:x

d(s) = 0

d(x) = 5

d(u) = 8

d(y) = 7

d(v) = 9

pi(s) = nedef

pi(x) = s

pi(u) = x

pi(y) = x

pi(v) = u

Se selecteaza si marcheaza v

N-a mai ramas de relaxat nici un arc algoritmul se opreste.Din valorile lui pi si d putem extrage caile cele mai usoare:

I la s: [s] cu greutatea w([s]) = d(s) = 0I la x : [s, x ] cu greutatea w([s, x ]) = d(x) = 5I la u: [s, x , u] cu greutatea w([s, x , u]) = d(u) = 8I la y : [s, x , y ] cu greutatea w([s, x , y ]) = d(y) = 7I 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 pi calculata de algoritmul lui Dijkstra determina un arboreGpi cu radacina s, n care fiecare nod x 6= s are parintele pi(x).Exemplu (Arborele Gpi pentru digraful simplu ponderat G ilustrat)

s

x

u y

v

5

23

1

Observatie

Orice ramura a lui Gpi 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},

vV

f (u, v) = 0.

f (u, v) se numeste fluxul net de la nodul u la v . Valoarea fluxuluif este |f | =vV f (s, v), adica, fluxul total de retea care pleacadin 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 esteuV

f (u,v)>0

f (u, v)

Fluxul pozitiv de retea care pleaca dintr-un nod v esteuV

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

v2

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 sumaxX

yY

f (x , y).

f (u,X ) reprezinta sumaxX

f (u, x).

f (Y , u) reprezinta sumayY

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 = atunciI 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, atuncisuma 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/1

6

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

vV(f + f )(u, v) =

vV

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

=vV

f (u, v) +vV

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

In final avem ca|f + f | =

vV

(f + f )(s, v) =vV

(f (s, v) + f (s, v)) =vV

f (s, v) +vV

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

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 maximn 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 Gf5 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

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/1

6

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

Analiza complexitatiiUn exemplu care dureaza (E |f |)

s

u

v

t100

0000

1000000

1

1000000

100000

0

(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

t100

0000

1000000

1

1000000

100000

0

(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.

2 Se calculeaza un flux maxim de la s la t.

Curs 9


Construirea unei retele de flux pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

s t

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

Teorema

Fie G reteaua de flux 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


Construirea unei retele de flux pentru un graf bipartit:

Exemplu

x1

x2

x3

x4

x5

y1

y2

y3

y4

s t

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

Teorema

Fie G reteaua de flux 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)Ef (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

limbaje algoritmi

Documents

Transcript of limbaje algoritmi