Descriere
Cuvant-inainte
Grafurile sunt modele matematice abstracte, folosite pentru a descrie relatiile dintre obiecte discrete. Ele reprezinta instrumente puternice de rezolvare a multor probleme, cum ar fi: urmarirea fluxului monetar al unei tari, rutarea de pachete pe internet, proiectarea retelelor telefonice, realizarea sistemelor software, utilizarea motoarelor de cautare pe web, biologia moleculara, automatizarea planificarii rutiere, calculul stiintific etc. Puterea grafului este data de faptul ca solutia la o problema teoretica poate fi utilizata pentru a rezolva probleme practice dintr-o mare varietate de domenii.
Ideea dupa care a fost alcatuita cartea, sugerata chiar de titlul ei, este aceea de a familiariza cititorul cu acele abilitati de modelare matematica, astfel incat rezolvarea proiectelor propuse sa fie concretizata prin intermediul calculatorului.
Fara o parcurgere succinta a rezultatelor teoretice ce se regasesc in fiecare capitol ar fi mai dificila intelegerea algoritmilor analizati, pentru care s-a scos in evidenta complexitatea lor în diverse situatii de implementare.
Lucrarea este impartita in doua parti: prima cuprinde principalele notiuni si teoreme de caracterizare a grafurilor, precum si un studiu detaliat al modalitatilor de memorare si traversare a acestora. De asemenea, aici se regasesc principalele rezultate privind arborii de traversare, drumurile optime, dar si aspecte referitoare la grafurile hamiltoniene si cele euleriene.
In partea a doua sunt cuprinse probleme din domeniul retelelor de flux, teoria cuplajelor, colorarea grafurilor si analiza grafurilor planare si a grafurilor aleatoare.
ln ultimul capitol din partea a doua sunt prezentate succint facilitatile oferite de doua biblioteci interactive de grafuri: MATGRAPH si Boost Graph Library.
Cartea se adreseaza unui cerc larg de cititori preocupati in activitatea lor de probleme de optimizare: matematicieni, ingineri, economisti, studenti, elevi din clasele terminale de liceu. Totodata, ea poate constitui un material auxiliar pretios pentru perfectionarea profesorilor de informatica din invatamantul preuniversitar, dar si in pregatirea unor activitati de laborator in specializarile cu profil informatic din invatamantul superior.
Parcurgerea cartii implica din partea cititorului familiarizarea lui anterioara cu noţiuni elementare legate de tehnici de programare si structuri de date. Nu sunt lipsite de importanta cunostintele despre reprezentarea datelor in memorie si notiuni generale de alocare dinamica a memoriei. Biblioteca STL ofera o mare varietate de structuri secventiale de date, utilizarea ei este prezenta in implementarea unui numar semnificativ de algoritmi din lucrare.
Din cele peste 300 de probleme propuse, la aproape 90 dintre ele au fost date rezolvarile complete, insotite si de exemple de executie. In vederea evaluarii celor mai bune performante ale algoritmilor analizati, s-a incercat prezentarea mai multor variante de implementare, folosind in acest sens structuri de date diferite.
In capitolul I se regasesc definitiile elementare: graf complet, graf bipartit, graf regulat, grafuri izomorfe etc. De asemenea, sunt introduse notiunile de graf partial, subgraf, supergraf, precum si principalele operatii pe grafuri. Tot aici sunt prezentate notiunile de lant, lant simplu, lant elementar, ciclu, drum, circuit, graf conex, graf tare conex. Multe din problemele propuse sau rezolvate in cadrul acestui capitol se bazeaza pe teoremele lui Euler si, respectiv, Havel-Hakimi.
In capitolul II sunt analizate grafurile prin prisma unor rezultate din algebra liniara. Matricele de adiacenta/incidenta, matricele ciclurilor/ciclurilor fundamentale au multe aplicatii in stiinta si inginerie; tocmai din acest motiv, regasim aici cateva teoreme ce ofera o caracterizare matematica riguroasa a grafurilor.
In capitolul III sunt date proprietati remarcabile si teoreme corespunzatoare arborilor cu radacina. Sunt analizaţi doi algoritmi importanti utilizati in matematica si informatica(Kruskal, Prim) prin care se pot determina arborii de acoperire de cost minim in grafurile ponderate; de asemenea, regasim un caz particular de arbori minimi de acoperire si anume arborii Steiner, cu o larga aplicabilitate in electronica. Capitolul se incheie prin demonstrarea teoremei lui Cayley privind enumerarea arborilor(demonstratie datorata lui H. Prilfer) si implementarea corespunzatoare acestei demonstraţii.
In capitolul IV sunt analizati cei mai importanti algoritmi de parcurgere a grafurilor. Utilizarea acestora conduce uneori la obtinerea unor rezultate cu un efort de calcul mai mic decat daca am folosi calculul matriceal direct. Ambii algoritmi produc arbori de latime, respectiv arbori de adancime, o caracterizare a acestora fiind data in teorema parantezelor, respectiv teorema drumului alb. Pe baza celor doi algoritmi sunt analizate cateva rezolvari complete ale unor probleme frecvent intalnite, cum ar fi: determinarea conexitatii, a componentelor conexe/tari conexe, sortarea topologica a varfurilor unui graf, determinarea punctelor de articulatie, a muchiilor critice, determinarea excentricitatii si a diametrului unui graf.
Capitolul V abordeaza probleme de drumuri optime; sunt analizati algoritmii: Dijkstra, Dantzig, Bellman-Ford, Bellman-Kalaba. De asemenea, pentru problema drumurilor optime corespunzatoare tuturor perechilor de varfuri, este analizat algoritmul Roy-Floyd-Warshall.
Pentru determinarea drumurilor optime in grafuri rare s-a scos in evidentă importanta utilizarii algoritmului lui Johnson. Tot in cadrul capitolului V sunt descrise si exemplificate notiunile de centru relativ, centru absolut si mediana unui graf.
Dupa parcurgerea primelor patru capitole este recomandata utilizarea bibliotecilor interactive MATGRAPH şi BGL prezentate in capitolul XI. Aici este oferit un material didactic ce exploateaza foarte elegant facilitatile grafice oferite de mediul de programare MATLAB, astfel incat cititorul isi poate insusi foarte repede cunostintele de baza despre grafuri neorientate neponderate.
Programarea generica este recomandata la rezolvarea problemei de reutilizare pentru biblioteci de grafuri. Prin programarea generica, algoritmii pe grafuri devin mult mai flexibili, astfel incat sa permita utilizarea lor cu usurinta in aplicatii diverse. Scrierea unui algoritm generic pe grafuri are avantajul suplimentar de a fi mai natural; abstractia inerenta din descrierea in pseudocod a algoritmului este retinuta in functia generica.
Boost Graph Library(BGL) este prima biblioteca scrisa in C++ care utilizeaza conceptul de programare generica pentru implementarea notiunii de graf; dezvoltarea acesteia a plecat de la faptul ca STL nu ofera toate facilitatile pentru memorarea si efectuarea unor operatii pe grafuri. Astfel, in BGL se extinde notiunea de iterator si cea de functor din STL. Avand in vedere ca mediile de programare MATLAB si C++ sunt bine cunoscute, consideram ca, prin utilizarea acestor biblioteci, punem la dispozitia cititorului instrumente foarte elegante de lucru. Aceasta mai ales daca tinem seama ca implementarea algoritmilor pe grafuri este o activitate complexa. Pentru o parte din algoritmii foarte laboriosi, cum ar fi algoritmul lui Johnson, a fost facuta doar o prezentare generala. Din considerente de spatiu, implementarile nu au fost prezentate; in schimb ele pot fi apelate din biblioteca BGL.
Tocmai datorita dificultatilor de implementare a unor algoritmi de grafuri, am considerat necesara prezentarea in cele 10 capitole a unor implementari detaliate ale acestora. Cititorul are de ales intre dezvoltarea propriilor proiecte pe baza programelor prezente in carte sau apelarea directa la bibliotecile de grafuri.
Pentru grafurile hamiltoniene, in capitolul VI sunt prezentate o serie de teoreme(Dirac, Ore, Bondy-Chvatal) de caracterizare, dar si cativa algoritmi importanti. In general algoritmii pentru determinarea ciclurilor hamiltoniene sunt de complexitate nepolinomala. Pentru grafuri de dimensiuni mici o variantă ar fi: utilizarea metodei backtracking, algoritmul lui Foulkes reduce problema determinarii ciclurilor hamiltoniene la determinarea unor drumuri hamiltoniene in componentele tare conexe ale grafului, algoritmul lui Kaujfman utilizabil in cazul grafurilor tare conexe. O atentie speciala este acordata problemei comis-voiajorului, care din punct de vedere matematic revine la determinarea permutarii optime a celor n varfuri ale grafului. Pe langa rezolvarea clasica prin backtracking am considerat util sa explicam modul cum se utilizeaza un algoritm aproximativ mult mai performant.
In partea a doua a capitolului este data teorema lui Euler privitoare la determinarea ciclurilor euleriene intr-un graf. Sunt prezentati aici doi algoritmi importanti: algoritmul lui Fleury(dupa deplasarea pe o muchie a grafului, aceasta se elimina din graf), algoritmul lui Hierholzer(determinarea unor cicluri distincte, dar care sa aiba un varf comun si reuniunea acestor cicluri).
Algoritmul lui Christofides este o varianta de determinare a unui ciclu hamiltonian de cost minim intr-un graf in care ponderile muchiilor satisfac inegalitatea triunghiului din spatiul euclidian.
O alta problema importanta este cea cunoscuta sub numele de problema postasului chinez: determinarea unui traseu minim care sa traverseze fiecare muchie cel putin o data.
Capitolul VII trateaza grafurile orientate de tip retea. In cadrul capitolului putem urmari cateva teoreme de analiza a retelelor, ce sunt grafurile reziduale si ce este un drum de ameliorare intr-o reţea. Sunt analizati algoritmii Ford-Fulkerson(inclusiv varianta Edmonds-Karp) si algoritmul lui Dinic pentru determinarea unui flux maxim intr-o retea. De asemenea se face o analiza a implementarii teoremei de flux maxim taietura minima. Tot in cadrul acestui capitol se prezinta modalitatile de determinare a unui cuplaj perfect folosind algoritmul Edmonds-Karp si problema cuplajului maxim de cost minim tratata ca o problema de flux maxim. Pentru intelegerea notiunilor legate de cuplaj intr-un graf este necesara parcurgerea primelor doua sectiuni din capitolul VIII. In secţiunea VII.8 sunt prezentate drumurile critice in grafurile de activitati. De exemplu, pentru executarea unui proiect complex, diferitele activitati trebuie sa fie bine coordonate pentru a evita piererea de timp si bani, activităţi pe care le putem reprezenta printr-un graf de tip retea. Doua metode foarte asemanatoare pentru rezolvarea acestei probleme, numite Critical Path Method(CPM) si Project Evaluation and Review Technique(PERT) au fost dezvoltate intre anii 1956 si 1958 de doua grupuri diferite.
Capitolul VIII prezinta algoritmi legati de cuplaje in grafuri. Pe langa notiunile teoretice strict necesare cum ar fi: lant alternant, multime transversala, sunt enuntate si cateva teoreme importante cum ar fi cele datorate lui Berge, Hali, Tutte, Konig. Sunt analizati doi algoritmi pentru determinarea unui cuplaj maxim cu ajutorul unei retele de transport.
Algoritmul ungar datorat lui H W. Khun este implementat in doua variante folosind parcurgerile DF/BF pe grafuri. Algoritmul Hopcroft-Karp de complexitate O( n5 ), in cazul grafurilor dense de ordin n, este cel mai performant algoritm pentru determinarea unui cuplaj maxim; acesta foloseste ambele metode de parcurgere a grafurilor. Cu ajutorul algoritmului Kuhn-Munkres se poate determina un cuplaj maxim de cost minim intr-un graf bipartit.
Capitolul IX este dedicat problemelor de colorare a grafturilor, probleme care in cazurile generale sunt NP-dificile. Lui G. Birkhoff i se datoreaza o teorema importanta pe baza careia putem deduce o metoda recursiva pentru determinarea polinomului cromatic, polinom ce reprezinta un invariant asociat unui graf (o implementare a acestui algoritm este data în [75]). Referitor la colorarea varfurilor unui graf, remarcabila este teorema lui Brooks. Problema colorarii muchiilor unui graf se reduce la problema colorarii varfurilor grafului adjunct asociat. Referitor la colorarea muchiilor unui graf, importante sunt rezultatele date in teorema lui Vizing, cu ajutorul careia putem realiza si o clasificare a grafurilor.
Sunt prezentati cativa algoritmi clasici de colorare a varfurilor unui graf cum ar fi: Welsh- Powell, SL-color, DSATUR, GIS. Implementarea acestora este realizata prin subprograme corespunzatoare fiecarei metode si care returneaza colorarea gasita, pentru ca, în functia principala, sa fie selectata din rezultatele obtinute acea metoda care ofera colorarea cea mai buna. In IX.3 sunt prezentate cateva probleme din teoria extremala a grafurilor, mai intâi se prezinta teorema lui Turan referitoare la grafuri p-partite complete, apoi teorema lui Ramsey.
Capitolul X este dedicat grafurilor planare si grafurilor aleatoare. Teorema lui Euler referitoare la grafuri planare este un rezultat important in caracterizarea acestora. Alte rezultate foarte importante ce caracterizeaza grafurile planare sunt formulate in teorema lui Kuratowski, teorema lui Wagner si teorema lui Grinberg.
Testarea planaritatii unui graf este o problema dificila de mare actualitate; in acest sens, pe langa aspectele teoretice cuprinse in teoremele menţionate mai sus, sunt dati si cativa algoritmi pentru testare a planaritatii ce utilizeaza si aceste rezultate: Hopcroft-Tarjan, Tutte, Schnyder. In sectiunea X.6 se prezinta relatia dintre un graf si dualul sau; a colora fetele unui graf planar revine la a colora varfurile grafului sau dual.
Secţiunea X.8, ce cuprinde rezultatele formulate in teorema celor cinci culori(a carei demonstratie se datorează lui P.J. Heawood) si teorema celor patru culori care afirma ca orice graf planar este 4 colorabil, incheie sectiunile referitoare la grafuri planare.
Secţiunile X.9-X. ll din cadrul acestui capitol sunt dedicate grafurilor aleatoare. Am considerat necesara prezentarea acestor tipuri de grafuri intrucât prin intermediul lor ne putem testa modul cum se comporta diversi algoritmi pentru grafuri de dimensiuni mari, imposibil de generat daca nu folosim calculatorul.
Modelul Erdâs Renyi, strans legat de grafurile generate aleator, stabileste ca o mulţime de muchii sau arce sa aiba varfurile intre fiecare pereche de varfuri cu aceeasi probabilitate, independent de celelalte muchii(arce).
Grafurile aleatoare standard pot fi generate eficient atat in termeni de timp si spatiu, utilizand un generator de numere aleatoare performant precum generatorul Mersenne Twister.