flux maxim în rețele de transportandrei.clubcisco.ro/cursuri/f/f-sym/2pa/cursuri/2012cb/curs 11...
Post on 02-Nov-2019
1 Views
Preview:
TRANSCRIPT
5/16/2011
1
Flux maxim în rețele de transport
5/16/2011
2
2
5/16/2011
3
Definiții și proprietăți
• Rețea de transport– Graf orientat
– Capacitate
– Sursă și scurgere
• Flux
• Proprietăți– Restricție de capacitate
– Antisimetrie
– Conservare flux
• Valoarea fluxului
3
5/16/2011
4
4
5/16/2011
5
Fluxul în rețea
5
∑∑∈∈
==
VvVv
tvfvsff ),(),(||
5/16/2011
6
Exemplu |f|
|f| = f(s, v1) + f(s, v2) + f(s, v3) + f(s, v4) + f(s, t) =
11 + 8 + 0 + 0 + 0 = 19
|f|= f(s, t) + f(v1, t) + f(v2, t) + f(v3, t) + f(v4, t) =
0 + 0 + 0 + 15 + 4 = 19
6
5/16/2011
7
Mai multe surse și destinații
7
5/16/2011
8
Rețeaua reziduală a lui G indusă de f conține
arcele NxN pentru care valoarea de mai jos
(capacitatea arcului respectiv) este pozitivă
8
),(),(),( vufvucvuc f −=
5/16/2011
9
Exemplu de rețea reziduală
9
5/16/2011
10
Drum de ameliorare
10
}în este ),( :),(min{)( pvuvucpc ff =
5/16/2011
11
Capacitatea drumului de ameliorare=4
11
5/16/2011
12
Metoda Ford-Fulkerson
Cât timp există un drum de ameliorare
repetă mărește fluxul de-a lungul lui
12
5/16/2011
13
Exemplu
13
Cut
5/16/2011
14
Tăietură
14
5/16/2011
15
Fluxul prin tăietura (S,T)
f(S,T) = 12 – 4 + 11 = 19
15
∑∈∈
=
TvSu
vufTSf,
),(),(
5/16/2011
16
Capacitatea unei tăieturi (S,T)
c(S,T)= 12+ 0 + 14 = 26
16
∑∈∈
=
TvSu
vucTSc,
),(),(
5/16/2011
17
17
Capacitatea maximă a rețelei este de cel mult 12 + 7 + 4 = 23
(tăietura minimă)
5/16/2011
18
Fluxul
18
5/16/2011
19
Teorema de flux maxim, tăietură minimă
• Dacă f este un flux în G=(N,A), cu sursă s și
scurgere t, atunci condițiile sunt echivalente:
1. f este un flux maxim în G.
2. Rețeaua reziduală nu conține căi de ameliorare.
3. |f| = c(S,T) pentru o tăietură (S,T) (minimă).
19
5/16/2011
20
Algoritmul Ford-Fulkerson
20
5/16/2011
21
21
5/16/2011
22
22
5/16/2011
23
Analiză
23
O(E)
O(E)
?
5/16/2011
24
Analiza
• Capacitati intregi – marire a |f| cu ≥ 1.
• Daca fluxul max e f*, atunci ≤ |f*| iterations � time is O(E|f*|).
• Note that this running time is not polynomialin input size. It depends on |f*|, which is not a function of |V| or |E|.
• If capacities are rational, can scale them to integers.
• If irrational, FORD-FULKERSON might never terminate!
24
5/16/2011
25
26
5/16/2011
26
27
5/16/2011
27
• Repetă de 999,999 ori
28
5/16/2011
28
Edmonds-Karp
• Căutare în lățime pe rețeaua reziduală �Calea de ameliorare
este cea mai scurtă cale în rețeaua reziduală
• O(na2)
29
5/16/2011
29
Edmonds-Karp
• 2 iterații
30
top related