Algoritmi de optimizare in grafuri

Algoritmi de optimizare in grafuri

     Tematica grafurilor şi fluxurilor este una dintre cele mai răspândite, intuitive şi uşor de asimilat. Chiar dacă nu toţi dintre noi realizăm în mod imediat, multe din lucrurile ce ne înconjoară au legătură cu acest domeniu: şoselele ce unesc oraşele unei tări, construirea economică şi judicioasă a unei reţele de distribuire în teritoriu a curentului electric repartizarea releelor de retransmisie a semnalului telefoniei mobile/tv/…, reţelele de severe împreună cu distribuirea datelor şi sarcinilor între acestea, etc.          De fapt, cam tot ce înseamnă „reţea de …” are legătură aproape în mod nemijlocit cu teoria grafurilor. Bineînţeles că mai ales acum, când concurenţa pe orice piaţă, de orice fel este mai acerbă decât oricând fiecare competitor încearcă să-l surclaseze pe celălalt prin calitate şi preţ scăzut. De multe ori acest lucru se traduce prin adjectivele: eficienţă, optimizare. Ori, teoria grafurilor exact de asta se ocupă. Pentru cei ce sunt interesaţi de teoria grafurilor lucrarea de faţă este un ajutor în acest sens. Ea reuneşte unele dintre noţiunile de bază despre grafuri şi fluxuri şi rezultatele mai importante. Este scrisă îngrijit şi face domeniul ceva mai uşor de înţeles. În afară de prezentarea noţiunilor de bază, a definiţiilor, teoremelor şi algoritmilor, lucrarea pune la dispoziţia celor interesaţi şi codul scris într-un limbaj de programare – Turbo Pascal – limbaj prezent în programa şcolară din învătământul preuniversitar. Astfel se constituie într-un instrument util (şi pentru) elevii de liceu. În afară de probleme de optim - drum minim/maxim în grafuri, este atinsă şi noţiunea de flux. Mai ales acum, noţiunea de flux - în contextul informaţiei care „pleacă” dintr-un loc către altul utilizând diferite medii de transmisie, este mai actuală ca oricând. Câţi dintre cei ce utilizează un calculator nu s-au gândit sau nu au auzit măcar odată sintagma „flux de date”?          În lucrare sunt teoretizate câte lucruri despre flux maxim. Cu alte cuvinte lucrarea este un instrument util pentru cei ce doresc să se familiarizeze cu acest domeniu.                                                                                                       lect.dr. Vlad Monescu                 Lucrarea abordează două capitole mari din teoria grafurilor: Algoritmi de drum minim şi 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 doua 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ăietură 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.

Spune-ti opinia