Scurt istoric al teoriei grafurilor

Scurt istoric al teoriei grafurilor

Jocurile si amuzamentele matematice au fost punctul de plecare a ceea ce numim astazi "teoria grafurilor". Dezvoltandu-se la inceput paralel cu algebra, aceasta ramura a stiintei a capatat in timp atat forma cat si continut propriu, devenind un tot unitar bine conturat si bine fundamentat teoretic, cu o larga aplicare practica.

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

"Data nasterii" a teoriei grafurilor poate fi considerata anul 1736, cand matematicianul elvetian Leonard Euler a publicat in revista "Comentarii Academiae Scientiarum Imperiali Petropolitanae" un articol in limba latina.

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-ne pe notiuni care astazi fac parte din domeniu teoriei grafurilor fizicianul Kirchoff a studiat retelele electrice contribuind in mod decisiv la dezvoltarea teoriei electricitatii in (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, chimie organica, 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.

In scopul familiarizarii cu diversele domenii de aplicare, prezentam cateva probleme "clasice" a caror rezolvare implica notiuni legate de teoria grafurilor.

Se pune problema construirii unei sosele intre doua localitati notate cu 1 si respectiv 8, care ar putea sa treaca prin localitatile 2,.,7. cunoscand costul lucrarii pentru fiecare dintre tronsoanelor ce lega doua localitati, astfel incat costul general al lucrarii sa fie cat mai mic.

Daca localitatile se figureaza prin puncte, iar portiunile de sosea prin curbe, se obtine figura , care este de asemenea un graf.

Trei muncitori trebuie sa fie repartizati sa lucreze pe trei masini. Se cunoaste randamentul fiecarui muncitor pe fiecare masina in parte si se doreste stabilirea unei repartizari a muncitorilor pe fiecare masina astfel incat sa se obtina un maxim de randament. Notand cu 1, 2 si 3 cei trei muncitori, cu a, b si c cele trei masini si cu linii drepte posibilitatile de asociere dintre fiecare muncitor si fiecare masina, se obtine reprezentarea sub forma unui graf. Evident, daca o legatura nu este trasata, inseamna ca muncitorul nu are calificarea necesara pentru a putea lucra pe masina respectiva.

Iesirea din labirint

Labirintele sunt constructii stravechi, primele referiri la ele intalnindu-se in mitologie. Mai tarziu s-au construit labirinte din garduri vii in gradinile si parcurile 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 XIX, a demonstrat ca unui labirint i se poate asocia 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, parcurgand un traseu care sa fie, eventual, cat mai scurt.

Problema protocolului

La un dineu oficial participa 2n persoane, fiecare dintre acestea avand printre invitati cel mult n-1 persoane cu care nu este in relatii de prietenie. Pentru reusita intalnirii, organizatorii trebuie sa aseze la masa fiecare persoana, astfel incat fiecare sa aiba ca vecini numai persoane cu care sa se aiba in relatii bune.

Problema datoriilor

Intr-un grup sunt mai multe persoane, care au unele fata de altele, diverse datorii. Pentru achitarea datoriilor, fiecare persoana poate plati sume datorate, urmand ca sa primeasca, la randul sau, sumele cuvenite de la datornici. Procesul se poate bloca daca exista persoane care nu dispun de intreaga suma pe care o datoreaza altora, desi suma pe care o poseda ar acoperii diferenta intre suma datorata si cea cuvenita. In cazul in care sumele disponibile sunt suficiente, ar trebui sa se stabileasca subgrupurile de persoane care au datorii reciproce, pentru reglementarea datoriilor in cadrul subgrupului.

In exemplele date, prin folosirea unor puncte si a unor legaturi intre acestea, figurate prin segmente, problemele din practica s-au transformat in probleme ce tin de teoria grafurilor.