Drumuri hamiltoniene într-un graf

Notiuni fundamentale

Teoria grafurilor este o parte a matematicii cu varii domenii de aplicabilitate, printre acestea numarandu-se problemele de micro si macroeconomie (organigrame), fizică (retelele de distribuire a energiei electrice sau termice), comunicaţii (retelele de transport rutier sau feroviar), problemele de elaborare a deciziilor, de lingvistica, de energie electrica sau chimica, de psihologie (sociograme), de retele de calculatoare sau suport tehnic pentru Internet si multe altele.

Intuitiv, un graf este o figură formată din puncte legate între ele prin săgeţi. Punctele simbolizează elemente diferite (în funcţie de fenomenul modelat prin graf) – indivizi, colectivităţi, evenimente, acţiuni, operaţii. Săgeţile reprezintă legăturile ce se stabilesc între elementele considerate.

Prima lucrare despre grafuri apartine reputatului matematician elvetian Leonhard Euler, care a studiat si apoi a dat un verdict in renumita (pe atunci) problema a Podurilor

din Konigsberg. Orasul Konigsberg (azi Kaliningrad), pe atunci in Prusia Orientala, este asezat pe malurile si pe doua insule ale raului Pregel. Legatura intre partile orasului este asigurata de sapte poduri. O problema matematica ce figura ca nerezolvata de ani buni era sa se gaseasca o modalitate de a parcurge intregul oras, trecand pe toate podurile, o singura data. Euler este cel care in anul 1736 a demonstrat ca problema nu se poate rezolva, iar demonstratia sa a pus bazele teoriei grafurilor. Cu aceasta ocazie, euler a explicat de ce o astfel de parcurgere a orasului nu este posibila, nu numai in cazul Podurilor din Koningsberg, ci si in cazul oricarei retele compuse din poduri. Euler a demonstrat ca parcurgerea este posibila doar daca fiecare zona de pamant este conectata printr-un numar par de de poduri sau daca plimbarea incepe dintr-o parte si se incheie in alta parte a orasului.

O alta problema clasica de teoria grafurilor se numeste Problema colorarii hartilor care cere ca , fiind data o harta cu n tari, sa se determine toate solutiile de colorare a hartii, utilizand cel mult patri culori, astfel incat doua tari de frontiera comuna sa fie colorate diferit. Aceasta problema dateaza de multe sute de ani, de cand cei care se ocupau de desenarea hartilor au descoperit, empiric, ca daca se doreste colorarea hartii unei tari, impartita in regiuni, saunt de ajuns patru culori diferite astfel incat doua tari alaturate sa nu fie colorate la fel. Demostrarea matematica a ceea ce se stia deja apartine lui Heawood care, in 1890, a aratat ca problema este general valabila daca in loc de “patru” culori se folosesc “cinci” culori.

O mare parte din problemele economice, ce se modeleza cu ajutorul grafurilor si retelelor, conduc la asa-numita problema a drumului hamiltonian, un drum ce trece prin toate varfurile unui graf (retele) cate o singura data. Termenul a fost atribuit dupa numele matematicianului William Hamilton, care in 1857 a inventat un joc ce folosea un

dodecandru – un poliedru cu 12 fete, fiecare fata fiind un pentagon regulat , iar in ficare din cele 20 de varfuri se intalnesc trei muchii.Fiecare varf al dodecandruluilui Hamilton era marcat cu numele unui oras important: Bruxelles, Canton, Delhi, Frankfurt. Jocul consta in a gasi un drum de-a lungul muchiilor dodecandrului care sa treaca prin fiecare oras exact o data si sa se intoarca in orasul din care a plecat. Ordinea trecerii prin primele orase era stabilita de la inceput.Pentru memorarea trecerilor efectuate, in fiecare varf al dodecandrului era cate un cui cu o floare mare, astfel incat in jurul acestor cuie putea sa se intinda un fir care sa indice drumul parcurs in aceasta calatorie imaginara in jurul lumii.