Grafuri euleriene și hamiltoniene

Profesor indrumator: Cuprins 1. Grafuri euleriene 2. Grafuri hamiltoniene 3. Bibliografie Grafuri euleriene Adeseori suntem tentati sa credem simplul fapt de a traversa strazi sau poduri nu implica nici o idee deosebita. Iata insa ca exista o celebra problema de traversare in care singura idee implicata este aceea de traversare, problema celor sapte poduri din Konigsberg. Aceasta banala si totusi foarte controversata problema a dus la aparitia si dezvoltarea teoriei grafurilor.

Problema se pune cam asa: figura 1. Oamenii care cutreierau aceste insule au observat ca daca porneau de pe malul sudic al raului, nu puteau sa-si planifice plimbarea astfel incat sa traverseze fiecare pod o singura data. Se parea ca ori trebuia sa sara un pod ori sa-l traverseze de doua ori.

In anul 1735 Euler a descoperit ca nu mai are rost sa se incerce, propunand urmatoarea analiza a problemei, din punct de vedere matematic: Sa consideram mai intai insula estica (fig. 2.) : sunt trei poduri care duc la ea. Deoarece se pleaca de pe malul sudic, inseamna ca se pleaca din afara insulei estice. Deoarece fiecare din cele trei traversari trebuie efectuate o singura data, plimbarea trebuiesa se termine pe insula estica. Sa consideram acum insula vestica: sunt cinci poduri care duc pe ea, iar cinci este din nou numar impar. Asadar plimbarea incepe in afara insulei, si deci trebuie sa se termine pe insula vestica.

Aceasta inseamna ca plimbarea se termina in doua locuri diferite simultan ceea ce e imposibil. Solutia data de Euler este tipica pentru personalitatea si ingeniozitatea sa. Tot el a scris in anul 1736 prima lucrare de teorie a grafurilor despre problema acestor sapte poduri.

Un ciclu al unui graf G care contine toate muchiile lui G se numeste ciclu eulerian.

Un graf G care are un ciclu eulerian se numeste graf eulerian.

Un graf G fara varfuri izolate este eulerian daca si numai daca este conex si gradele tuturor varfurilor sale sunt numere pare.

Din punct de vedere al teoriei grafurilor, problema se pune cam asa: cele patru regiuni (insule si maluri) A, B, C, D si cele sapte poduri le reprezentam in graful urmator (fig. 3.) : Muchiile grafului reprezentand posi-bilitatile de trecere de pe un mal pe un pod si reciproc.

Ciclu eulerian: Fiind dat un graf neorientat, sa se verifice daca este graf eulerian si in caz afirmativ, sa se determine un ciclu eulerian al sau. Explicatia programului: Pornim dintr-un varf neizolat retinut cu ajutorul variabilei prim, in cadrul procedurii de citire, apoi cautam un ciclu eulerian al grafului printr-un algoritm backtracking. Vom folosi pentru retinerea ordinii varfului in ciclul eulerian un sir s.

In cadrul procedurii de cititre a matricii de adiacenta, numaram si muchiile grafului cu ajutorul variabilei m.

Functia valid verifica daca varful k apartine ciclului eulerian (daca este adiacent cu varful anterior determinat, iar in cazul in care este ultimul varf k=m ...