GRAFURI

Florea DanPodar Răzvan

DEFINIȚIE

• Numim graf o pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate).

• În primul caz, graful se numește neorientat, iar în cel de-al doilea orientat.

Graf neorientat

Graf orientat

ISTORIC

• Graful este la origine un concept matematic. • Teoria grafurilor are o vechime mult mai mare

comparativ cu informatica.• În informatică graful este privit ca o structură

de date.

• O particularitate a grafurilor în informatică este faptul că de fiecare dată sunt considerate grafuri finite (cu număr finit de noduri).

• Informatica a preluat noţiunile teoriei grafurilor imaginând o multitudine de situaţii concrete rezolvabile cu algoritmi ce prelucrează structuri asimilate grafurilor.

Euler Leonhard• Născut la Basel (Elvetia) în

1707, s-a remarcat ca fizician şi matematician.

• Se apreciază că a fost figura predominantă a sec. XVIII în domeniul matematicii.

• Euler este printre cei mai prolifici autori în specialitatea sa, publicând pe parcursul vieţii peste 70 volume.

• Moare în anul 1783 la St. Petersburg, Rusia.• A avut contribuţii decisive în demonstrarea

unor teoreme matematice, în teoria numerelor, a funcţiilor trigonometrice şi desigur, a grafurilor.

• În 1736, Euler Leonhard publica lucrarea “Soluţia problemei prin geometria poziţiei” în care a stabilit o abordare noua a problemei “Celor 7 poduri din Koenigsberg” (Poduri peste râul Pregel din Koenigsberg – localitate din Prusia sec. XVIII ).

PROBLEMA PODURILOR

• Să se găsească dacă este posibil, o modalitate de traversare a tuturor celor 7 poduri (notate de la “a” la “g”) parcurgându-le o singura dată pe fiecare, cu reîntoarcere în locul de plecare. Notaţia “A” – “D” reprezintă porţiuni de uscat.

• Problema podurilor poate fi “transcrisă” folosind notaţii specifice teoriei grafurilor prin utilizarea unor segmente (ce marchează calea de urmat) şi cercuri (ce marchează intersecţia unor căi figurate prin segmente).

EXEMPLE DIN VIAȚA REALĂ

• Cel mai bun exemplu de aplicaţie practică în viaţa reala a grafurilor neorientate sunt hărţile rutiere.

• Putem afla astfel cel mai scurt drum până într-un anumit punct sau care puncte de pe hartă sunt cel mai uşor accesibilile. Nodurile pot fi considerate oraşe, iar muchiile drumuri; grafurile orientate pot reprezenta drumuri cu sens unic intre clădiri.

• De asemenea, ne putem reprezenta traiectoria unei călătorii cu ajutorul unui lanț al unui graf neorientat.

• Grafurile mai pot arăta legăturile dintre anumite grupuri sau oameni; grafurile orientate pot arăta transferul de informații sau a unor bunuri.

• Un arbore genealogic este de asemena un graf neorientat (de tip arbore, mai exact).

• Cablurile de înaltă tensiune care pornesc dintr-o centrală pot fi și ele reprezentate cu ușurință cu ajutorul unui graf orientat, indicând și direcția de deplasare a curentului. În acest caz centrala este un nod sursă.

• La fel se poate reprezenta și un sistem de canalizare, de încălzire sau rețeaua de apă curentă.

• Multitudinea căilor aeriene reprezintă grafuri. Nodurile sunt intersecțiile (imaginare) și muchiile sunt rutele (imaginare). Noduri pot fi și aeroporturile.

• Teoria grafurilor este folosită în domenii variate: de la chimie la economie, de la studiul reţelelor electrice la critica textelor de politică, devenind o disciplina majoră.

Bibliografie

• Ro.wikipedia.org• Scribd.com• Caiet informatica clasa XI

VĂ MULȚUMIM PENTRU ATENȚIE!