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