Algoritmi de optimizare in grafuri - Ciprian Ghise

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)