Elemente de teoria grafurilor

Jocurile si amuzamentele matematice au fost punctual de plecare in ceea ce astazi numim”teoria grafurilor.Dezvoltandu-se la inceput paralel cu algebra,aceasta ramura a stiintei a capatat in timp lorma si continut propiu,devenind un tot unitari bine conturat si bine fundamental teoretic ,cu larga aplicare practica.

Printre primii care s-au ocupat de acest domeniu au fost Konig si Berge.Acestia au stabilit primele notiuni de limbaj specific domeniului.

,,Data nasterii” teoriei grafurilor poate fi considerata anul 1736,cand matematicianul elvetian Leonhard Euler a publicat in revista ,,Comentarii Academiae Scientiarum Imperialis Petropolitanae”un articol in limba Latina(Solutio problematic ad geometriam situs pertinentis-Solutia unei probleme legate de geometria pozitiei) in care a clarificat ,,problema celor sapte poduri”,stabilind astfel o metoda pentru rezolvarea unei intregi clase de probleme.

Concret, problema este urmatoarea:raul Pregel imparte orasul Koenigsberg(astazi Kaliningrad),prin care trece, ca in figura 5.1.

Portiunile de uscat, notate A,B,C si D sunt unite intre ele prin sapte poduri notate a,b,c,d,e,f si g.Intrebarea pe care si-a pus-o Euler a fost daca este posibil ca,plecand dintr-un punct ,sa se poata trece pe toate podurile, cate o singura data, revenindu-se in final in punctual de plecare. Figura 5.2

Daca se figureaza portiunile de uscat prin cerculete si podurile ca legaturi intre acestea,se obtine schita din figura 5.2, care este, de fapt, un graf.

Ca izvoare ale teoriei grafurilor mai pot fi considerate:fizica-studiul retelelor electrice-,geografia-problema colorarii hartilor cu cel mult patru culori-,chimia-principalul initiator fiind Cayley etc.

Bazandu-se pe notiuni care astazi fac parte din domeniul teoriei grafurilor,fizicianul Kirchoff

A studiat retelele electrice contribuind in mod decisive la dezvoltarea teoriei electricitatii(in 1845 a formulat legile care guverneaza circulatia curentului intr-o retea electrica,iar in 1847 a aratat cum poate fi construita intr-un graf o multime fundamentala de cicluri). Teoria grafurilor este o ramura destul de noua a teoriei multimilor,care s-a dovedit foarte utila si cu aplicatii in domenii variate:economie,chimieorganica,organizare,psihologie,anumite domenii ale artei etc.Grafurile ofera cele mai potrivite metode de a exprima relatii intre obiecte,de aceea aria lor de utilizare practica este foarte vasta,de la economie la psihologie sociala. Relatia graf-retea

In scopul familiarizarii cu diversele domenii de aplicare,prezentam cateva probleme,,clasice” a caror rezolvare implica notiuni legate de teoria grafurilor.Din analiza acestora,se constata ca notiune de graf utilizata in stabilirea aspectelor teoretice este ceea ce se desemneaza in practica prin notiune de retea. Retea rutiera

Se doreste construirea unei sosele intre doua localitati notate cu 0 si,respective 7,care ar putea sa treaca prin localitatile 1,2, ,6.Cunoscand costul lucrarii pentru fiecare dintre tronsoanele ce leaga doua localitati,trebuie sa se determine traseul soselei intre localitati,astfel incat costul general al lucrarii sa fie cat mai mic.Daca localitatile se figureaza prin cercuri ,iar portiunile de sosea prin linii,se obtine figura 5.3,care este,de asemenea,un graf.

Iesirea din labirint

Labirinturile sunt constructii stravechi,primele referiri la ele intalnindu-se in mitologie.Mai tarziu s-au construit labirinturile din garduri vii,in gradinile si parcurilor curtilor imperiale,pentru amuzament,dar si pentru frumusetea lor.Indiferent din ce materiale au fost construite, acestea presupun existenta unui numar de culoare separate intre ele,care se intalnesc in anumite puncte.Studiul lor,inceput la sfarsitul secolului al XIX-lea, a demonstrate ca unui labirint I se poate asocial un graf,in care varfurile corespund intersectiilor,iar muchiile culoarelor labirintului.O problema imediata ar fi aceea de a gasi iesirea din labirint,pornind dintr-un punct al sau si parcurgand un traseu care sa fie,eventual,cat mai scurt.

1. Daniela, Oprescu; Liana Bejan Ienulescu; Informatică – manual pentru clasa a XI-a, Editura Niculesu, 2006

2. Niculescu, St.; Cerchez, Emanuela; Şerban, Marinel; Bacalaureat şi atestat in informatică, Editura L&S Infomat, Bucureşti, 2000

3. Andonie Răzvan; Gârbacea, Ilie, Algoritmi fundamentali. O perspectivă C++, Editura Libris, Cluj-Napoca, 1995

4. Sorin, Tudor; Tehnici de programare. Manual pentru clasa a XI-a, Editura L&S, 1996