Algoritmi de optimizare in grafuri - Ciprian Ghise

Descriere

Lucrarea abordeaza doua capitole mari din teoria grafurilor: Algoritmi de drum minim maxim in grafuri si Fluxuri in retele. Lucrarea de fata este structurata in trei parti. Prima parte a lucrarii numita Notiuni introductive contine un scurt istoric al teoriei grafurilor precum si vocabularul de baza in teoria grafurilor. Partea a doua Distante si drumuri minime prezinta principalele probleme de drum minim si cinci algoritmi importanti de drum minim• algoritmul Dantzig, algoritmul Ford, algoritmul Dijsktra, algoritmul Bellman-Ford si algoritmul Floyd-Warshall. Partea a treia Fluxuri in retele incepe cu introducerea conceptelor necesare: retea, capacitate, flux, retea reziduala, taietura precum si a unor rezultate fundamentale, dupa care se continua cu doi algoritmi de determinare a fluxului maxim: algoritmul generic si algoritmul de etichetare Ford-Fulkerson. Algoritmii prezentati in lucrare sunt insotiti de teoreme care demonstreza corectitudinea lor, de o analiza a ordinului de complexitate, de exemple care faciliteaza intelegerea corecta si completa a lor, precum si de implementarea lor in limbajul Borland Pascal.

Fragment:

" Teorema 2.3. Algoritmul Bellman-Ford determina distantele d(s,y) si drumurile minime D syp, yE V, in raport cu varful sursa s din graful orientat G=(V,A) cu functia valoare v:A--> R.
Demonstratie. Pentru inceput aratam ca la al i -lea pas din ciclul repeta avem urmatorul rezultat: daca d(x)#infinit, atunci reprezinta valoarea unui drum de la s la x. Aratam prin inductie dupa numarul de iteratii a ciclului repeta . La iteratia 0 avem pasul 1 al algoritmului, care este evident. Fie iteratia i, consideram momentul cand distanta la un varf x d(x) este actualizata cu d(y)+v(y,x). Din ipoteza inductiei d(y) este valoarea unui drum de la s la y. Atunci d(y)+ valoarea arcului (y,x) este valoarea unui drum de la s la x care trece prin y.
Deoarece un drum de la varful s la oricare alt varf poate sa contina cel mult n-1 arce, rezulta ca, atunci cand nu exista circuite cu valoare negativa, corpul ciclului repeta se poate executa de cel mult n ori. Daca corpul ciclului repeat se executa si a n+1 oara atunci graful contine circuite cu valoare negativa.
Cand s-a ajuns la pasul 3 algoritmul determina drumurile minime de la varful sursa s catre toate celelalte varfuri, daca Presupunem ca d(x) nu reprezinta drumul minim de la s la x. Asta inseamna ca exista un arc (y,x) cu proprietatea ca d(y)+v(y,x)<d(x). Dar asta contrazice faptul ca iesirea din ciclul repeta se face cand, dupa o parcurgere a tuturor arcelor sirul d nu a suferit nici o modificare (adica nici o valoare d(x) nu mai poate fi micsorata). "