Algoritmi in retele de transport

Introducere …………………………………….……………….... 3
1.1.Reţele de transport şi fluxuri ………………….………..………. 3
1.2.Exemplu de reţea de transport ……………….…………...…….. 5
1.3.Reţele cu mai multe surse şi destinaţii ………….…………..….. 8
1.4.Însumarea fluxului ……………………………..……………… 10

1.Metoda lui Ford-Fulkerson .............................................................. 12
1.1.Reţele reziduale ....................................................................... 12
1.2.Drumuri de ameliorare ............................................................ 14
1.3.Tăieturi în reţele de transport .................................................. 16
1.4.Algoritmul de bază Ford-Fulkerson ........................................ 18
1.5.Analiza algoritmului Ford-Fulkerson ...................................... 21

2.Algoritmi de preflux ........................................................................... 26
2.1.Aspecte intuitive ...................................................................... 26
2.2.Operaţii de bază ....................................................................... 28
2.3.Algoritmul generic ................................................................... 30
2.4.Corectitudinea metodei de preflux ........................................... 31
2.5.Analiza metodei de preflux ...................................................... 33

3.Algoritmul mutare-în-faţă .................................................................. 37
3.1.Muchii şi reţele admisibile ........................................................ 37
3.2.Liste de adiacenţă ...................................................................... 39
3.3.Algoritmul mutare-în-faţă ......................................................... 44
3.4.Analiza algoritmului ................................................................. 48

4.Aplicaţie pentru algoritmul Mutare-în-faţă .................................. 50
4.1.Codificarea datelor …………………………………………… 50
4.2.Rezultate obţinute ……………………………….……………. 51
Bibliografie...........................................................................................58
Anexă