Pagina documente » Informatica, Matematica » Fluxuri in retele. Metoda de etichetare a nodurilor pentru rezolvarea problemei de flux maxim

Despre lucrare

lucrare-licenta-fluxuri-in-retele.-metoda-de-etichetare-a-nodurilor-pentru-rezolvarea-problemei-de-flux-maxim
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-fluxuri-in-retele.-metoda-de-etichetare-a-nodurilor-pentru-rezolvarea-problemei-de-flux-maxim


Cuprins

CUPRINS
Introducere i
CAPITOLUL I
FLUX MAXIM iN RETELE.PROBLEMA DE BAZA
1. Notiuni 1
2. Fluxuri in retele 3
3. Notatii 5
4. Taieturi 6
5. Flux maxim 7
6. Multimi deconectoare si taieturi 12
7. Metoda de etichetare a nodurilor pentru rezolvarea problemei de flux maxim 13
8. Graf incrementat 18
9. Descompunerea fluxului 20
CAPITOLUL II
VARIATII ALE PROBLEMEI DE FLUX MAXIM
1. Intrari si iesiri multiple 24
2. Limitele inferioare ale fluxului pe arce 26
3. Fluxuri in retele ne-directionate si mixte 29
4. Capacitatile nodurilor si alte extensii 30
CAPITOLUL III
FLUX MINIM iN RETELE
1. Notiuni 35
2. Algoritmul lui Ford-Fulkerson 36
3. Exemplu 38
CAPITOLUL IV
FLUX DE COST MINIM DE LA s LA t
1. Un algoritm bazat pe determinarea circuitelor negative 52
1.1. Descrierea algoritmului 55
1.2. Exemplu 56
1.3. Pasul 3 al algoritmului din 1.1. 65
2.Algoritm de determinare a drumului cu flux de cost minim 66
2.1. Descrierea algoritmului 67
2.2 Exemplu 68
CAPITOLUL V
FLUXURI iN GRAFURI CU CiSTIGURI
1. Introducere 69
2. Augmenting chains 72
3. Cicluri active 75
4. Algoritmul aflarii fluxului optim pentru grafuri cu cistiguri 76
5. Exemplu 78
6. Grafuri cu cistiguri ale virfurilor 81
CAPITOLUL VI
APLICATII
1. Problema fluxului maxim 82
2. Problema de flux minim 88
Bibliografie 94
i

EXTRAS DIN DOCUMENT

?{p}

{p}

?

Introducere

Una din cele mai importante si interesante probleme care se poate rezolva cu ajutorul grafurilor este aceea de a determina valoarea fluxului maxim care poate fi transmis de la o sursa specificata s a unui graf, la un alt varf (iesire) t al grafului. Aceasta problema si variatiile ei pot fi aplicate intr-un numar mare de probleme practice, de exemplu in determinarea fluxului maxim a ratei de trafic intre doua localitati pe un drum reprezentat ca un graf.

O metoda de rezolvare a problemei de flux maxim intre s si t a fost realizata de Ford si Fulkerson si metoda lor de „etichetare”. Ford si Fulkerson au fost primii care au studiat problema fluxului maxim, au stabilit un numar de rezultate si au dezvoltat un algoritm pentru aflarea lui. Metoda lor originala nu a fost un algoritm pentru ca nu se termina intotdeauna. Edmonds si Karp au modificat aceasta metoda pentru a asigura terminarea procesului. Algoritmul modificat de ei avea complexitatea O(|N||A|2), pentru un graf G=(N,A). Multi altii au studiat problema fluxului maxim. Dinic a facut un algoritm de complexitate O(|N|2|A|) si mai tarziu Karzanov a imbunatatit tehnica lui Dinic, algoritmul lui are complexitatea O(|N|3). Între timp, acesti algoritmi au fost si mai mult imbunatatiti cu ajutorul unor tehnici sofisticate de structuri de date.

În literatura de specialitate au fost discutate cateva posibile variatii ale problemei de flux maxim de la s la t. Scopul acestei lucrari este sa descrie aceste probleme, sa arate relatiile dintre ele, si sa descrie algoritmii pentru rezolvarea lor.

Capitolul I, „Flux maxim in retele. Problema de baza” contine notiunile de baza, anumite notatii, enuntul problemei, teorema si algoritmul lui Ford-Fulkerson in cazul capacitatilor intregi, graful incrementat, teorema de descompunere a fluxului, impreuna cu exemple.

Capitolul II, „Variatii ale problemei fluxului maxim”, prezinta cazul intrarilor si iesirilor multiple, fluxuri cu limite inferioare pe arce, fluxuri in retele nedirectionate si mixte, capacitati in noduri.

Capitolul III, „Flux minim in retele”, prezinta problema fluxului minim, algoritmul lui Ford-Fulkerson si un exemplu.

Capitolul IV, „Fluxul maxim intre oricare pereche de varfuri”, prezinta echivalenta fluxului, condensarea varfurilor, un algoritm pentru determinarea fluxului maxim intre toate perechile de varfuri si un exemplu.

Capitolul V, „Flux de cost minim de la s la t”, prezinta un algoritm bazat pe determinarea ciclurilor negative, un algoritm care creste fluxul pe drumurile de cost minim din graful rezidual, descrierea acestora si exemple.

Capitolul VI , „Fluxuri in grafuri cu castiguri”, prezinta aceasta problematica, lanturile de marire a fluxului, ciclurile active, un algoritm pentru aflarea fluxului optim pentru grafuri cu castiguri cu exemple, si grafuri cu castiguri ale varfurilor.

Capitolul VII, „Aplicatii”, prezinta o implementare in limbajul PASCAL a algoritmilor Ford-Fulkerson pentru rezolvarea problemei fluxului maxim si a problemei fluxului minim, impreuna cu exemple de rulare.

CAPITOLUL ?