Grafuri euleriene si hamiltoniene

Trimis la data: 2007-06-04 Materia: Informatica Nivel: Liceu Pagini: 11 Nota: / 10 Downloads: 2524
Autor: Oana Paul Dimensiune: 197kb Voturi: Tipul fisierelor: doc Acorda si tu o nota acestui referat: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
Adeseori suntem tentaţi să credem simplul fapt de a traversa străzi sau poduri nu implică nici o idee deosebită. Iată însă că există o celebră problemă de traversare în care singura idee implicată este aceea de “traversare”, problema celor şapte poduri din Königsberg. Această banală şi totuşi foarte controversată problemă a dus la apariţia şi dezvoltarea teoriei grafurilor.

Problema se pune cam aşa:
Oraşul Königsberg era aşezat pe coasta Mării Baltice, la gurile râului Pregel. Pe râu erau două insule legate de ţărmuri şi între ele de şapte poduri ca în
figura 1.

Oamenii care cutreierau aceste insule au observat că dacă porneau de pe malul sudic al râului, nu puteau să-şi planifice plimbarea astfel încât să traverseze fiecare pod o singură dată. Se părea că ori trebuia să sară un pod ori să-l traverseze de două ori.
În anul 1735 Euler a descoperit că nu mai are rost să se încerce, propunând următoarea analiză a problemei, din punct de vedere matematic:
Să considerăm mai întâi insula estică (fig.2.):

sunt trei poduri care duc la ea. Deoarece se pleacă de pe malul sudic, înseamnă că se pleacă din afara insulei estice. Deoarece fiecare din cele trei traversări trebuie efectuate o singură dată, plimbarea trebuiesă se termine pe insula estică.

Să considerăm acum insula vestică:
sunt cinci poduri care duc pe ea, iar cinci este din nou număr impar. Aşadar plimbarea începe în afara insulei, şi deci trebuie să se termine pe insula vestică.
Aceasta înseamnă că plimbarea se termină în două locuri diferite simultan ceea ce e imposibil.
Soluţia dată de Euler este tipică pentru personalitatea şi ingeniozitatea sa. Tot el a scris în anul 1736 prima lucrare de teorie a grafurilor despre problema acestor şapte poduri.

Un ciclu al unui graf G care conţine toate muchiile lui G se numeşte ciclu eulerian. Un graf G care are un ciclu eulerian se numeşte graf eulerian.
Un graf G fără vârfuri izolate este eulerian dacă şi numai dacă este conex şi gradele tuturor vârfurilor sale sunt numere pare.
Din punct de vedere al teoriei grafurilor, problema se pune cam aşa: cele patru regiuni (insule şi maluri) A,B,C,D şi cele şapte poduri le reprezentăm în graful următor (fig.3.):

Muchiile grafului reprezentând posi-bilităţile de trecere de pe un mal pe un pod şi reciproc.
Problema are soluţie dacă acest graf conţine un ciclu eulerian. Un astfel de ciclu, utilizează la fiecare trecere printr-un vârf două muchii ce nu mai pot fi folosite pentru o nouă trecere. Cum fiecare dintre cele patru vârfuri (A,B,C,D) au grade impare, rezultă că ultima muchie va rămâne nefolosită sau va fi folosită pentru a face trecerea de final ( pentru a încheia plimbarea). Aceasta ar însemna că ori va rămâne la unul din vârfuri, o muchie nefolosită (fapt ce demonstrează că nu avem un ciclu eulerian) ori plimbarea ar trebui să se termine în mai multe locuri simultan ceea ce e iarăşi imposibil.
Ciclu eulerian: Fiind dat un graf neorientat, să se verifice dacă este graf eulerian şi în caz afirmativ, să se determine un ciclu eulerian al său.

Explicaţia programului:

Pornim dintr-un varf neizolat reţinut cu ajutorul variabilei prim, în cadrul procedurii de citire, apoi căutăm un ciclu eulerian al grafului printr-un algoritm backtracking. Vom folosi pentru reţinerea ordinii vârfului în ciclul eulerian un şir s.
În cadrul procedurii de cititre a matricii de adiacenţă, numărăm şi muchiile grafului cu ajutorul variabilei m.
Funcţia valid verifică dacă vârful k aparţine ciclului eulerian (dacă este adiacent cu vârful anterior determinat, iar în cazul în care este ultimul vârf k=m dacă este adiacent cu primul vâfr al ciclului).

Procedura back caută succesiv, autoapelându-se, vârfuri adiacente cu vârful anterior determinat până când se ajunge la ultimul vârf al ciclului (k=m); în acest caz, variabila booleană găsit care a fost iniţializată pe false, ia valoarea true şi este tipărit şirul s încheindu-l cu primul vârf al său (pentru a arăta că este un ciclu).
Dacă nu a fost găsit nici un ciclu eulerian al grafului dat (găsit=false), atunci graful nu este eulerian şi se tipăreşte mesaj.

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Filmele zilei
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10 Bacalaureat 2019 Vezi subiectele examenului de Bacalaureat din 2019 Evaluare Nationala 2019 Ultimele informatii despre evaluare nationala
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles