Cartea Algoritmi de optimizare in grafuri PDF

Lucrarea abordează două capitole mari din teoria grafurilor: Algoritmi de drum minim maxim în grafuri și Fluxuri în rețele. Lucrarea de față este structurată în trei părți. Prima parte a lucrării numită Noțiuni introductive conține un scurt istoric al teoriei grafurilor precum și vocabularul de bază în teoria grafurilor. Partea a două Distanțe și drumuri minime prezintă principalele probleme de drum minim și cinci algoritmi importanți de drum minim• algoritmul Dantzig, algoritmul Ford, algoritmul Dijsktra, algoritmul Bellman-Ford și algoritmul Floyd-Warshall. Partea a treia Fluxuri în rețele începe cu introducerea conceptelor necesare: rețea, capacitate, flux, rețea reziduală, tăietura precum și a unor rezultate fundamentale, după care se continuă cu doi algoritmi de determinare a fluxului maxim: algoritmul generic și algoritmul de etichetare Ford-Fulkerson. Algoritmii prezentați în lucrare sunt însoțiți de teoreme care demonstreză corectitudinea lor, de o analiză a ordinului de complexitate, de exemple care facilitează înțelegerea corectă și completă a lor, precum și de implementarea lor în limbajul Borland Pascal. Fragment: " Teorema 2.3. Algoritmul Bellman-Ford determină distanțele d(s,y) și drumurile minime D syp, yE V, în raport cu vârful sursa s din graful orientat G=(V,A) cu funcția valoare v:A--> R. Demonstrație. Pentru început arătăm că la al i -lea pas din ciclul repetă avem următorul rezultat: dacă d(x)#infinit, atunci reprezintă valoarea unui drum de la s la x. Arătăm prin inducție după numărul de iterații a ciclului repetă . La iterația 0 avem pasul 1 al algoritmului, care este evident. Fie iterația i, considerăm momentul când distanța la un vârf x d(x) este actualizată cu d(y)+v(y,x). Din ipoteza inducției 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 vârful s la oricare alt vârf poate să conțină cel mult n-1 arce, rezultă că, atunci când nu există circuite cu valoare negativă, corpul ciclului repetă se poate executa de cel mult n ori. Dacă corpul ciclului repeat se execută și a n+1 oară atunci graful conține circuite cu valoare negativă. Când s-a ajuns la pasul 3 algoritmul determină drumurile minime de la vârful sursa s către toate celelalte vârfuri, dacă Presupunem că d(x) nu reprezintă drumul minim de la s la x. Asta înseamnă că există un arc (y,x) cu proprietatea ca d(y)+v(y,x)