algoritmica grafurilor 6

7/29/2019 Algoritmica grafurilor 6

1/12

83

Capitolul 6PROBLEME DE FLUXURI N REELE

6.1. Problema fluxului maximNumim reea (de transport) cu intrarea s i ieirea t, 4 uplul

R = (G,s,t,c) unde: G = (V, E) este un digraf; G Gs, t V, s t, d (s) 0, d (t) 0+ > > ; c : E , c(e)R+ este capacitatea arcului e.

Vom presupune c

V = {1, 2, ..., n} ( n N )i c

|E| = m.Extindem funcia c la

c : V V R+

prin:c(ij), ij E

c((i, j))0, ij E

=

i vom nota c((i,j)) = ijc .

Definiie. Numim flux n reeaua R = (G,s,t,c) o funciex : V V R care satisface

(i) ij ij0 x c , ij V V ;(ii) ji ij

j V j Vx x 0, i V {s, t}

= .

Dac ij E atunci ijx se numetefluxul(transportat) pe arcul ij.

Evident, condiia (i) cere ca fluxul pe orice arc s fie nenegativ isubcapacitar, iar condiia (ii) (legea de conservare a fluxului)cere ca sumafluxurilor pe arcele care intr n vrful is fie egal cu suma fluxurilor pearcele care ies din vrful i.

Cu convenia fcut la extensia funciei de capacitate, se observ

c pentru perechile (i, j)care nu sunt arce n reea condiia (i) impune cafluxul s fie 0, i evident cele doua definiii sunt echivalente.

Dac se sumeaz relaiile (ii) (pentru i V {s, t} ) se obine:


2/12

84

ji ij ji iji s, t j V j V i s, t j s, t i s, t j s, t

si ti is it is si it ti

i s, t i s, t i s, t i s, t i i i i

0 x x x x

x x x x x x x x ,

= = +

+ + =

Definiie. Dac x este un flux n reeaua R = (G,s,t,c) se numetevaloarea fluxului x numrul

jt tjj V j V

v(x) x x

= .

v(x) se poate interpreta ca fiind fluxul net care ajunge n ieirea reelei sau(conform egalitii obinute mai sus) fluxul net care iese din intrarea reelei.

n orice reea R = (G,s,t,c) exist un flux, fluxul nul ijx 0 ij= , de

valoare 0.Problema fluxului maxim

Dat R = (G,s,t,c) o reea, s se determine un flux de valoare maxim.Problema se poate formula, ca o problem de programare liniar:

ji ijj j

js sjj j

jt tjj j

ij ij

maxv

x x 0, i s, t

x x v

x x v

0 x c ij

=

= =

Definiie. Dac P este un drum n G , multigraful suport al digrafuluiG, i i je v v= este o muchie a lui Patunci:

- dac e corespunde arcului i jv v al lui G, e se numete arc directaldrumului P;

- dac e corespunde arcului j iv v al lui G, atunci e se numete arcinvers.Definiie. Fie R = (G,s,t,c) i x flux n R. Se numete C-drum(n R

relativ la fluxul x) un drum D n G cu proprietatea c ij E(D) :ij ijx c< dac ij este arc direct;

jix 0> dac ij este arc invers.


3/12

85

Dac D este un C drum i ij E(D) , se numete capacitaterezidual a lui ij (relativ la C drumul D) numrul

ij ij

ji

c x , ij arc direct n Dr(ij)

x , ij arc invers n D.

=

Capacitatea rezidual a drumului D este:

e E(D)r(D) min r(e)

= .

Definiie. Se numete drum de cretere a fluxului x, n reeaua R =(G,s,t,c), un C-drum de la s la t.

Se arat c:Lem.Dac D este un drum de cretere a fluxului x n reeaua R = (G,s,t,c),

atunci 1x x r(D)= definit prin

ij1ij ij

ij

x , ij E(D)

x x r(D), ij E(D), ij arc direct n D

x r(D), ji E(D), ji arc invers n D

= +

este flux n Ri 1v(x ) v(x) r(D)= + .Rezult c dac x admite un drum de cretere atunci x nu este flux de

valoare maxim.Definiie. Fie R = (G,s,t,c). Se numete seciune n reeaua R, o

partiie (S,T) a lui V cu s S i t T .Capacitatea seciunii (S,T) este

iji S j Tc(S,T) c =

(suma capacitilor arcelor de la S la T).Se arat c:Lem.Dac x este un flux n R = (G,s,t,c) i (S,T) este o seciune a reelei,

atunci

ij jii S j T

v(x) (x x )

=

(valoarea fluxului este egal cu fluxul net ce trece prin orice seciune)Lem. Dac x este un flux n R = (G,s,t,c) i (S,T) este o seciune,

atunci v(x) c(S,T).Teorem. (Teorema drumului de cretere)Un flux x este de valoare maxim ntr-o reea R, daci numai dac,

nu exist drumuri de cretere a fluxului x n reeaua R.


4/12

86

S observm c i S i j T avem:

- dac ij E atunci ij ijx c= i

- dac ji E atunci jix 0=

(altfel, C-drumul de la s la i se poate extinde la un C-drum de la s la j).Deci, conform lemei precedente:

ij ji iji S j T i S j T

v(x) (x x ) (c 0) c(S,T)

= = =

i prin urmare x este flux de valoare maxim.Teorem. (Teorema fluxului ntreg)Dac toate capacitile sunt ntregi, atunci exist un flux de valoare

maxim cu toate componentele ntregi (flux ntreg de valoare maxim).Demonstraie.Fie algoritmul

1: 0x 0; i 0;

2: while (iP drum de cretere relativ la

ix ) do

{

i 1 iix x r(P )

+ ;

i + +

}

Se observ c ix are componente ntregi este un invariant alalgoritmului (din definiia lui ir(P ) , dac toate capacitile sunt ntregi,

rezult ci

r(P ) este ntreg n ipoteza c ix este ntreg) i c la fiecare

iteraie a pasului 2 valoarea fluxului curent crete cu mcar o unitate, decipasul 2 se repet de cel mult c({s}, V {s}) Z+ ori. Fluxul final obinut

este de valoare maxim.Observaie. Algoritmul, descris mai sus, este finit i n cazul

capacitilor raionale.Teorem. ( Ford-Fulkerson)Valoarea maxim a unui flux n reeaua R =(G,s,t,c) este egal cu

capacitatea minim a unei seciuni a reelei.Demonstraie.

Dac dispunem de un algoritm care, pornind de la un flux iniial0

x( 0x exist ntotdeauna, de exemplu 0x = 0), construiete ntr-un numr finitde pai un flux x, care nu admite drumuri de cretere, atunci seciunea


5/12

87

construit n demonstraia teoremei antecedente satisface mpreun cu xenunul teoremei.

Pentru cazul capacitilor raionale algoritmul descris satisfaceaceast condiie.

Pentru cazul capacitilor reale exist un algoritm, datorat lui

Edmonds i Karp.Algoritmul lui Ford i Fulkerson pentru aflarea unui flux de

valoare maximSe va folosi un procedeu de etichetare a vrfurilor reelei, n vederea

depistrii drumurilor de cretere a fluxului curent x. Dac nu exist drumuride cretere, fluxul va fi de valoare maxim.

Eticheta atribuit unui vrf j V are trei componente 1 2 3(e ,e ,e )

unde 1e V {0} , 2e {direct, invers}; 3e R+ i au urmtoarea

semnificaie:- dac 2e = direct i 1e i= atunci

un C-drum P de la s la j cu ultimul arc ij, arc direct i r(P) = 3e ;

- dac 2e = invers i 1e i= atunci

un C-drum P de la s la j cu ultimul arc ij, arc invers i r(P) = 3e .

Iniial, se eticheteaz sursa s cu eticheta (0, . , ) . Celelalte vrfuriprimesc etichet prin cercetarea vrfurilor deja etichetate:

Dac i este un vrf etichetat, atunci j V :- dac j neetichetat,

ij E i ij ijx c<

atunci j se eticheteaz3 ij ije (i,direct, min(e [i], c x ))= ;

- dac j neetichetat,ji E i jix 0>

atunci j se eticheteaz

3 jie (i, invers,min(e [i], x ))= .

Evident, n acest fel se respect semnificaia celor trei componenteale etichetelor.

Numim aceast proceduretichetare(i).Atunci cnd n procedura de etichetare s-a atribuit etichet vrfului t,

s-a obinut un drum de cretere P a fluxului curent, de capacitate rezidual

3r(P) e [t]= i ale crui vrfuri se depisteaz n O(n) explornd prima

component a etichetelor. Modificarea fluxului x r(P) se execut n acestmers napoi, tot n O(n).


6/12

88

Pentru noul flux se reia procedura de etichetare.Dac toate vrfurile etichetate au fost cercetate i nu s-a reuit

etichetarea vrfului t, rezult c fluxul curent nu admite drumuri de cretere,este deci de valoare maxim, iar dac S = mulimea vrfurilor etichetateatunci (S, V S) este o seciune de capacitate minim.

Descrierea algoritmului

1. Se alege x =ij(x ) flux ini

ial (de exemplu fluxul nul);

Se eticheteaz s cu (0, . , ) .2. while ( vrfuri etichetate necercetate) do

{

alege un vrf etichetat i necercetat i;

etichetare(i);

if (t a primit etichet) then

{

modific fluxul pe drumul dat de etichete;

terge toate etichetele;

eticheteaz s cu (0, . , )

}}

3. S {i i are etichet}T V S

x este flux de valoare maxim.

(S,T) este seciune de capacitate minim.

Complexitatea algoritmuluiPentru fiecare cretere a fluxului, sunt necesare cel mult 2m (m = |E|)

inspecii de arce n vederea etichetrii.Dac toate capacitile sunt ntregi atunci vor fi necesare cel mult v

(v = valoarea fluxului maxim) creteri succesive. Rezult c algoritmul are

complexitatea O(mv).Dac U este o margine superioar a capacitilor arcelor atunci

v (n 1)U((n 1)U este o margine superioar a capacitii seciunii

({s}, V {s})),deci algoritmul are complexitatea

O(nmU).Dezavantajele algoritmului sunt legate de neconvergena n cazul

capacitilor iraionale (dei practic, n implementri nu este cazul), i defaptul ca mrimile capacitilor influeneaz comportarea sa, acesteaneconstituind o msur a volumului datelor de intrare.


7/12

89

6.2. Fluxuri de cost minimFie R = (G,s,t,c) o reea i x un flux de la s la t n R.Considerm a : E R o funcie de cost care asociaz fiecrui arc

ij E , ija(ij) a= costul (transportului unei uniti de flux) pe arcul ij.

Costul fluxului x se definete ca fiindij ij

i, ja(x) a x= .

Problema fluxului de cost minim

Dat R o reea, v R+ i a : E R funcie de cost, s se determine0x flux n R astfel nct

{ }0a(x ) min a(x) x flux n R, v(x) v= = .Observm c, dac v nu depete valoarea fluxului maxim n reeaua

R, atunci problema are ntotdeauna soluii, a(x) fiind liniar, iar mulimea

fluxurilor de valoare dat v fiind mrginiti nchis nm

R .Definiie. Fie x un flux n R = (G,s,t,c) i a : E R o funcie decost.

Dac P este un C-drum n R relativ la fluxul x, atunci costul drumuluiP se definete

ij jiij P ij P

ij direct ij invers

a(P) a a

= .

Dac C este un C-drum nchis, a(C) se calculeaz dup aceeaiformul, dup stabilirea unui sens de parcurgere a lui C (este posibil caambele sensuri de parcurgere ale lui C s satisfac definiia unui C-drum).

1. Din definiia dat, rezult c dac P este drum de cretere relativ lafluxul x, atunci 1x x r(P)= este un flux de valoare 1v(x ) v(x) r(P)= + ide cost a(x) r(P) a (P)+ .

2. Dac C este un C-drum nchis relativ la x, atunci 1x x r(C)= esteun flux de valoare 1v(x ) v(x)= i de cost 1a(x ) a(x) r(C) a(C)= + .

Dac a(C) < 0 atunci 1x este un flux de aceeai valoare ca i x, dar decost strict mai mic.

Teorem.Un flux de valoare v este de cost minim daci numai dac nu admite

C - drumuri nchise de cost negativ.Demonstraie.

Necesitatea este evident din observaia anterioar.


8/12

90

Suficiena. Fie x un flux de valoare v, care nu admite C - drumurinchise de cost negativ.

Fie x un flux de valoare v, de cost minim astfel nct

(x, x ) min{ (x, x ') x ' = flux de valoare v i cost minim}

unde { }ij ij(x, x ') | ij x x ' | = .Dac (x, x ) 0 = rezult c x x= i deci x este de cost minim.

Dac (x, x ) 0 > , fie ij astfel nct ij ijx x . Presupunem

ij ij ij0 x x c < (astfel, raionamentul este similar). Din legea de conservare

a fluxurilor rezult c

jk E astfel nct jk jk jk0 x x c <

sau

kj E astfel nct kj kj jk 0 x x c < .

Repetnd acest raionament, deoarece numrul vrfurilor este finit, seva obine C, un C-drum nchis relativ la x n R.

Considernd sensul invers de parcurgere pe C se obine un C-drum

C' , nchis relativ la x .Deoarece a(C) 0 din ipotez, iar a(C') = a(C), rezult, din

necesitatea teoremei ( x este de cost minim), c a(C) = 0.

Modificnd fluxul x cu ( C' ) pe C' , unde

kj kj jk jk kj direct n C ' kj invers n C '(C ') min{ min x x , min x x }

=

se obine un flux x ' cu

v(x ') v(x ) v= = , a(x ') a(x ) (C ') a(C ') a(x ) = + = ,

deci de cost minim, dar, cu (x,x ') (x,x ) < , contradicie.

Deci (x, x ) 0 = .Teorem.Dac x este un flux de valoare v i de cost minim iar 0P este un drum

de cretere, astfel nct

0a(P ) min{a(P)= P drum de cretere relativ la x}atunci 1 0x x r(P )= este un flux de valoare

10v(x ) v r(P )= + i de cost

minim.


9/12

91

Linia demonstraiei este urmtoarea: presupunnd prin reducere la

absurd c 1x nu este de cost minim, atunci 1x admite un C drum nchis Cde cost negativ. Cum x era flux de cost minim rezult c 0E(C) E(P ) 0 / .

Dac 0ij E(C) E(P ) , atunci va rezulta c 0P C ij conine un

drum de cretere relativ la x de cost mai mic dect 0P .Un drum de cretere de cost minim poate fi depistat cu ajutorul

algoritmilor de drum minim.Dac x este un flux n R i a : E R este funcia de cost atunci

considernd ija = dac ij E (caz n care ijx 0= ), construim

ij ij ij ji

ij ji ij ij jiij

ji ij ij ji

ij ij ji

a , x c i x 0

min{a , a }, x c i x 0a

a , x c i x 0

, x c i x 0

< =

< >=

= >

= =

Un drum de pondere minim de la s la t n raport cu ponderile ija

corespunde unui drum minim de cretere n R relativ la fluxul x.Un circuit de pondere negativ n raport cu ponderile ija corespunde

unui C drum nchis n R relativ la x, de cost negativ.Rezult, urmtorul algoritm pentru rezolvarea problemei fluxului de

cost minim.Algoritm generic de rezolvare a problemei fluxului de cost minim{

0: Se consider x = (ijx) un flux cu valoarea v ' v ;

{x poate fi fluxul nul sau un flux y determinat cu

ajutorul algoritmului de flux maxim i apoi

considernd vx yv(y)

= }

1: while ( circuite de pondere < 0 relativ laija ) do

{ determin un astfel de circuit;

modific fluxul pe acest circuit

}

2: while v(x) < v do

{ aplic un algoritm de drum minim n raport cu

ponderileija pentru depistarea unui C drum

P de cost minim;

x x min(r(P), v v(x)) }

}


10/12

92

Complexitatea pentru pasul 2 este O( 3n v) , dac se pleac de lafluxul nul. Se poate dovedi c pasul 1 se poate implementa astfel ca numrul

iteraiilor s fie O( 2nm log n ).n continuare se prezint o nou descriere a algoritmului lui Ford i

Fulkerson i se aplic acest algoritm pe un exemplu.

6.3. Algoritmul Ford-FulkersonAlgoritmul Ford-Fulkerson (denumit astfel dup L.R. Ford, Jr i

D.R. Fulkerson) calculeaz fluxul maxim ntr-o reea de fluxuri. A fostpublicat 1956.

Ideea algoritmului este foarte simpl: Atta timp ct exist un drumde la surs la int, cu capaciti disponibile pe toate muchiile drumului, vomtrimite flux pe unul din aceste drumuri. Se gsete, ulterior, un astfel de drumi aa mai departe. Un drum cu capaciti disponibile se numete drum decretere.

AlgoritmulSe d un grafG = (V,E), avnd capacitatea c(u,v) i fluxul f(u,v)=0

pentru muchia de la u la v. Vrem s gsim fluxul maxim de la sursas la intat. Dup fiecare pas al algoritmului se menin urmtoarele:

( ) ( )vucvuf ,, . Fluxul de la u la v nu depete capacitatea. ( ) ( )uvfvuf ,, = . Se menine fluxul net ntre u i v. Dac n

realitate a uniti trec de la u la v, iarb uniti trec de la v la u, meninem( ) bavuf =, i ( ) abuvf =, .

( ) ( ) ( )ufufvuf outinv

== 0, . Pentru toate nodurile u,

exceptndsi t. Fluxul ce intr ntr-un nod trebuie s fie egal cu cel ce iesedin nodul respectiv.

Aceasta nseamn c fluxul prin reea este ceea ce numim fluxlegal dup fiecare etap parcurs a algoritmului. Definim reeauarezidual ff EVG , ca fiindreeaua cu capacitate

( ) ( ) ( )vufvucvucf ,,, = i fr flux. A se ine cont de faptul c nu se tie cu certitudine c

fEE= ,

deoarece se poate ntmpla ca, trimind flux pe (u, v) acesta s se blocheze(satureze), ns d natere unei noi muchii (v, u) n reeaua rezidual.

Algoritmul Ford-FulkersonDate de intrare: Graful G cu capacitatea c, nodul surss i

nodul intt.Date de ieire: Un flux maximfde las la t


11/12

93

1. ( ), 0f u v pentru toate muchiile (u, v)2. Ct timp exist un drum Pde la s la t, astfel nct

( , ) 0fc u v > pentru toate muchiile ( ),u v P :

1. Gsirea ( ) ( ) ( ){ }min , ,f fc p c u v u v p=

2. Pentru fiecare muchie ( ),u v P 1. ( ) ( ) ( ), , ff u v f u v c p +

(Se trimite flux de-a lungul drumului)

2. ( ) ( ) ( ), , ff v u f v u c p

(Fluxul ar putea fi ntors ulterior)

Drumul poate fi gsit cu ajutorul, spre exemplu, metodei breadth-firstsearch sau al metodei depth-first search n graful ff EVG , . Dac se

folosete cel dinti, algoritmul se numeteEdmonds-Karp.Complexitate

Fluxul maxim va fi atins n momentul n care nu vor mai fi gsitedrumuri ce permit creterea fluxului corespunztor. Cu toate acestea, nuexist certitudinea unei astfel de situaii, astfel c singurul lucru ce se poategaranta este acela c, odat cu parcurgerea algoritmului, rezultatul este celcorect. n cazul n care algoritmul ruleaz la infinit, s-ar putea ntmpla cafluxul s nici nu convearg ctre fluxul maxim. Dar aceast se poatentmpla doar n cazul valorilor iraionale atribuite fluxului. Cndcapacitile sunt ntregi, timpul de rulare al algoritmului Ford-Fulkerson estede ordinul ( )O | E | f , unde |E| reprezint numrul de muchii ale grafului, iar

f reprezint fluxul maxim al grafului. Acesta deoarece fiecare drum decretere poate fi gsit ntr-un timp de ordinul ( )O | E | , mrind fluxul cu o

cantitate ntreag, care este cel puin 1.O variant a algoritmului Ford-Fulkerson , ce garanteaz finalitatea i

un timp de rulare independent de valoarea fluxului maxim, este algoritmul

Edmonds Karp, a crui timp de rulare este de ordinul 2O(| V || E | ) .ExempluUrmtorul exemplu indic primii pai ai algoritmului Ford-Fulkerson

ntr-o reea cu 4 vrfuri, sursa fiind A, iar inta (nodul terminal) D.Drumurile de cretere sunt gsite cu ajutorul metodei depth-first search(cutrii n adncime), unde vecinii sunt vizitai n ordine alfabetic. Acestexemplu imagineaz cel mai sumbru comportament al algoritmului. Lafiecare pas, este trimis un flux avnd valoarea 1 de-a lungul re elei. A sevedea c dac s-ar fi folosit o cutare de tipul breadth-first search, ar fi fostnevoie de doar doi pai.


12/12

94

Drum Capacitate Fluxul n reea rezultat

Fluxul iniial n reea

A,B,C,D

min(cf(A,B),cf(B,C),cf(C,D))= min(c(A,B)f(A,B),c(B,C) f(B,C),

c(C,D) f(C,D))= min(1000 0,1 0,1000 0) = 1

A,C,B,D

min(cf(A,C),cf(C,B),cf(B,D))= min(c(A,C) f(A,C),c(C,B) f(C,B),c(B,D) f(B,D))= min(1000 0,0 ( 1),1000 0) = 1

Dup nc1998 pai.

Reeaua final a fluxului

A se remarca modul n care fluxul este mpins napoi de la ClaB,n momentul n care se gsete drumulA, B, C, D.

algoritmica grafurilor 6

Documents