пятница, 2 декабря 2011 г.

Mai jos este explicată una dintre problemele teoriei grafurilor-problema Maze. O problemă Maze este o situație de trecere complexă printr-un labirint, prin care rezolvatorul trebuie să găsească ieșirea.


În istoria matematicii problema lui EULER despre podurile Königsberg sună în felul următor: peste rîul din  Königsberg sunt construite 7 poduri. Care este numărul optim de poduri care trebuie încă construit pentru a trece  singură dată peste fiecare pod. Soluția acestei probleme este numită prima teoremă a teoriei grafurilor. În prezent, această problemă face parte din cercetările altei ramuri ale matematicii-combinatorica
Soluția problemei:

Orașul este redus la un graf. Fiecare nod este colorat. Toate nodurile au un număr par de laturi.
Este posibil de efectuat drumuri euleriene dacă exact 0 sau 2 noduri au un număr par de laturi.
Al 9-lea pod se construiește între nodurile roșu și albastru, pentru a schimba paritatea fiecărui nod.
 Al 10-lea pod trebuie construit în așa mod, încît fiecare locuitor să se întoarcă în punctul inițial. Acesta este un circuit eulerian și impune condiția ca toate nodurile să fie de grad par. După ce s-a construit al 9-lea pod, nodurile roșu și oranj au grad par. Deci, paritatea lor trebuie schimbată prin adăugarea unui nod (pod) între ele.
În final obținem următoarea prezentare a podurilor din Königsberg:

четверг, 17 ноября 2011 г.

În matematică și informatică, teoria grafurilor studiază proprietățile grafurilor. Un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi atribuite direcții (în acest caz, se spune că graful este orientat). Vizual, un graf poate fi reprezentat ca o mulțime de puncte legate între ele prin linii (de obicei curbe).
Grafurile au o importanță imensă în informatică, de exemplu:
  • în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf;
  • schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;
  • în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări).