Grafuri euleriene si hamiltoniene

2x puncte

categorie: Informatica

nota: 5.73

nivel: Liceu

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[...]
DOWNLOAD REFERAT

Preview referat: Grafuri euleriene si hamiltoniene

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.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.
Confidentialitatea ta este importanta pentru noi

E-referate.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat termenii si conditiile de utilizare 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