subiect ul 08
TRANSCRIPT
-
7/24/2019 Subiect Ul 08
1/4
Subiectul 8
Fluxuri n retele
1 Preliminarii
Definitia 1 Numim retea de transport cu intrarea s si iesirea t, 4-uplul R= (G,s,t,c), unde:
- G=(V,E) este un digraf ;
- s, t V; s=t; d+G(s)> 0; d
G(t)> 0;
- c: E R+; c(e) se numestecapacitatea arcului e.
Obs. Presupunem V ={1, 2, . . . , n} si ca |E|= m. Extindem functiac la c : V V R+ prin:
c((i, j)) =
c(ij) daca ij E0 daca ij E
si vom nota c((i, j)) = cij.
Definitia 2 Se numeste flux n reteaua R= (G,s,t,c) o functiex: V V R, care satisface:
0 xij cij, ij v V (fluxul este nenegativ si subcapacitar)(1)
jV
xji jV
xij = 0, i V {s, t} (legea de conservare a fluxului)(2)
Obs. 1o Daca ij Eatunci xij se numeste fluxul transportat pe arcul ij.
Definitia 3 Daca x este un flux n reteauaR = (G,s,t,c)atunci se numestevaloarea fluxului xnumarul
v(x) =jV
xjt jV
xtj
Obs. 1o v(x) = fluxul net care ajunge n iesire = fluxul net care iese din intrare.2o In orice retea exista fluxul nul xij = 0, ij, de valoare 0.
2 Problema fluxului maxim
(PFM) DataR= (G,s,t,c) o retea, sa se determine un flux de valoare maxima.
Obs. Problema poate fi privita ca o problema de programare liniara, nsa numarul mare de restrictii(n + m, m + 1 variabile) si mai ales restrictiile de integritate pentru xij fac problema foarte dificila.
Motivarea problemeiA. Determinarea cuplajului maxim si a stabilei maxime ntr-un graf bipartitPentru graful bipartit G = (V1, V2; E) cu n varfuri si m muchii, consideram reteaua (G1, s , t, c), cu
V(G1) = {s, t} V1 V2; E(G1) = E1 E2 E3, E1 = {sv1 | v1 V1}, E2 = {v2t | v2 V2},E3= {v1v2| v1 V1, v2 V2, v1v2 E}, iar c: E(G1) Z+, definita prin:
c(e) =
1 daca e E1 E2 daca e E3
1
-
7/24/2019 Subiect Ul 08
2/4
Subiectul 8. Fluxuri n retele / DD / 2
Rezolvand problema fluxului maxim pe reteaua de mai sus, se determina n timp polinomial deterministun cuplaj de cardinal maxim n G.
B. Determinarea numarului de conexiune al unui grafFie un grafG= (V, E). Construim G1= (V(G1), E(G1)) astfel:
v V consideram av, bv V(G1) si avbv E(G1)
vw Econsideram bvaw, bwav E(G1)
c: E(G1) Z+, c(e) =
1 daca e = avbv altfel
Gasirea numarului de conexiune al lui G se face prin rezolvarea a |E(G)| probleme de flux n reteauaR= (G1, bs, at, c), unde Geste graful complementar al lui G.
Definitia 4 Daca P este un drum nM(G), multigraful suport al digrafului G, sie = vivj este o muchiea lui P, atunci: dacae corespunde arculuie = vivj al lui G, e se numestearc directal drumului P; dacae corespunde arcului e= vjvi al lui G, atuncie se numestearc invers.
Definitia 5 Fie R= (G,s,t,c) si x flux n R. Se numeste C-drum (n R relativ la fluxul x) un drumD nM(G) cu proprietatea caij E(D):
xij < cij daca ij este arc directxji > 0 daca ij este arc invers
DacaD este un C-drum si ij E(D), se numestecapacitatea reziduala a lui ij (relativ la C-drumulD) numarul
r(ij) =
cij =xij daca ij arc direct nDxji daca ij arc invers nD
Capacitatea reziduala a drumului D ester(D) = mineE(D) r(e).
Definitia 6 Se numestedrum de crestere a fluxului x, n reteauaR= (G,s,t,c), un C-drum de las lat.
Lema 1 Daca D este un drum de crestere a fluxului x n reteauaR= (G,s,t,c), atuncix1 =x r(D)definit prin
x1ij =
xij daca ij E(D)xij+ r(D) daca ij E(D), ij arc direct n Dxij r(D) daca ij E(D), ji arc invers n D
este flux n R siv(x1) = v(x) + r(D).
Obs. 1o Lema 1 justifica denumirile de drum de crestere si capacitate reziduala.2o Din definitie, daca D este drum de crestere, r(D) > 0 si deci avem v(x r(D)) > v(x). Rezulta
ca daca x admite un drum de crestere, x nu este flux de valoare maxima.
Definitia 7 FieR= (G,s,t,c). Se numeste sectiune n reteauaR, o partitie(S, T) a luiV cus S si
t T. Capacitatea sectiunii (S, T) este
c(S, T) =iS
jT
cij
(suma capacitatilor arcelor de la S laT).
Lema 2 Daca x este un flux nR= (G,s,t,c) si (S,T) este o sectiune a retelei, atunci
v(x) =iS
jT
(xij xji)
(valoarea fluxului este egala cu fluxul net ce trece prin orice sectiune.)
Lema 3 Daca x este un flux nR= (G,s,t,c) si (S,T) este o sectiune, atunciv(x) c(S, T).
-
7/24/2019 Subiect Ul 08
3/4
Subiectul 8. Fluxuri n retele / DD / 3
Obs. Daca x este un flux n R = (G,s,t,c) si (S, T) o sectiune astfel ncat v(x) = c(S, T), atuncixfluxn R, v(x) c(S, T) = v(x, deci x este flux de valoare maxima.
Teorema 1 Un flux este de valoare maxima ntr-o retea R nu exista drumuri de crestere a fluxuluix n reteaua R.
Demonstratie. Dacax este de valoare maxima si P ar fi un drum de crestere a lui x n R, atunci x =x r(P) ar
avea valoarea v(x) = v(x) + r(P) > v(x) (din Lema 1), contrazicand faptul ca x este de valoaremaxima.
Fie x un flux n Rcare nu admite drumuri de crestere. Consideram S= {i| i V si D C-drumn R de la s la i}. Evident, s S(exista D de lungime 0) si t S(nu exista C-drumuri de la s lat). Fie T =V S. Rezulta ca (S, T) este o sectiune. Sa observam ca i S sij T avem:
daca ij E , atunci xij =cij sidaca ji E , atunci xij = 0
(altfel, C-drumul de la s la i se poate extinde la un C-drum de la sla j ).
Deci, conform Lemei 2, v (x) =
iS
jT(xij xji) =
iS
jT(cij 0) = c(S, T)x flux de valoare maxima
Teorema 2 Daca toate capacitatile sunt ntregi, atunci exista un flux de valoare maxima cu toate com-ponentele ntregi.
Demonstratie. Se considera urmatorul algoritm:
begin1: x0:= 0; i:= 0;2: while( Pi drum de crestere relativ la x
i)do beginxi+1 :=xi r(Pi);i:= i + 1
endend.
Se observa ca:
- xi are componente ntregi este un invariant al algoritmului (din definit ia lui r(Pi), daca toatecapacitatile sunt ntregi r(Pi) este ntreg, n ipoteza ca x
i este ntreg)
- la fiecare iteratie a pasului 2, valoarea fluxului curent creste cu macar o unitate pasul 2 se repetade cel mult c({s}, V {s}) Z+ ori.
Fluxul final obtinut este, conform Teoremei 1, de valoare maxima. Obs. Algoritmul descris mai sus este finit si n cazul capacitatilor rationale.
Teorema 3 (Ford-Fulkerson, flux maxim sectiune minima)
Valoarea maxima a unui flux n reteaua R = (G,s,t,c) este egala cu capacitatea minima a uneisectiuni a retelei.
Demonstratie. Daca dispunem de un algoritm care, pornind de al un flux initial x0 (x0 existantotdeauna, de exemplu x0 = 0), construieste ntr-un numar finit de pasi un flux x, care nu admitedrumuri de crestere, atunci sectiunea construita n demonstratia Teoremei 1 satisface mpreuna cu xenuntul teoremei.
Pentru cazul capacitatilor rationale, algoritmul descris n demonstratia Teoremei 2 satisface aceastaconditie.
Pentru cazul capacitatilor reale, conform lui Edmonds si Karp, algoritmul Ford-Fulkerson cualege = parcurgere BFS satisface conditia.
Obs. Importanta algoritmica a Teoremei 3 este evidenta: multimea sectiunilor retelei este finita (desiexponentiala), pe cand multimea fluxurilor din retea este infinita.
-
7/24/2019 Subiect Ul 08
4/4
Subiectul 8. Fluxuri n retele / DD / 4
3 Algoritmul lui Ford si Fulkerson
Pentru aflarea unui flux maxim, se va folosi un procedeu de etichetare a varfurilor retelei, n vedereadepistarii drumurilor de crestere a fluxului curentx. Daca nu exista drumuri de crestere, fluxul va fi devaloare maxima.
Eticheta atribuita unui varfj Vare trei componente (e1, e2, e3), cu e1 V{0};e2 {direct, invers};
e3 R+ si au urmatoarea semnificatie:- daca e2 = direct si e1 = i, atunci un C-drum P de la s la j cu ultimul arc ij, arc direct, si
r(P) = e3;
- daca e2 = invers si e1 = i, atunci un C-drum P de la s la j cu ultimul arc ij, arc invers, sir(P) = e3;
Initial, se eticheteaza sursas cu eticheta (0, ., ). Celelalte varfuri primesc eticheta prin cercetareavarfurilor deja etichetate:
Daca i este un varf neetichetat, atuncij V:
- daca j neetichetat, ij E, xij < cij j primeste eticheta e= (i, direct, min(e3[i], cij xij));
- daca j neetichetat, j i E, xji > 0 j primeste eticheta e= (i, invers, min(e3[i], xji));
Evident, n acest fel se respecta semnificatia celor trei componente ale etichetelor. Numim aceasta
procedura etichetare(i).Atunci cand n procedura de etichetare s-a atribuit o eticheta varfului t, s-a obtinut un drum de
crestere P a fluxului curent, de capacitate reziduala r(P) = e3[t] si ale carui varfuri se depisteaza nO(n) explorand prima componenta a etichetelor. Modificarea fluxului x r(P) se executa n acest mersnapoi, tot n O(n).
Pentru noul flux se reia procedura de etichetare. Daca toate varfurile etichetate au fost cercetatesi nu s-a reusit etichetarea varfului t, rezulta ca fluxul curent nu admite drumuri de crestere, deci estede valoare maxima, iar daca S = multimea varfurilor etichetate, atunci (S, V S) este o sectiune decapacitate minima (conform Teoremei 1).
Descrierea algoritmului
begin
1: Se alege x= (xij) un flux initial (posibil fluxul nul); se eticheteaza scu (0, ., );2: while ( varfuri etichetate necercetate)do begin
alege un varf etichetat si necercetat i;etichetare(i);if (t a primit eticheta)then begin
modifica fluxul pe drumul dat de etichete;sterge toate etichetele;eticheteaza s cu (0, ., )
endend;
3: S:= {i| i V , i are eticheta};T :=V S;x este flux de valoare maxima;(S, T) este sectiune de capacitate minima;
end.
Complexitatea algoritmului: O(mv), unde m= |E|, v= valoarea fluxului maxim.Comentariu: Parcurgerea BFS a nodurilor etichetate (modificarea EdmondsKarp) conduce la
finitudine n cazul general (capacitati irationale). In aceasta situatie, complexitatea algoritmului devineO(m2n) (sau O(n5)), unde m= |E|, n= |V|.
* **