Grafurile in viata reala

Ion Andreea Stefania

Cel mai bun exemplu de aplicatie practica in viata reala a grafurilor neorientate sunt hartile rutiere. Putem afla astfel cel mai scurt drum pana intr-un anumit punct sau care puncte de pe harta sunt cel mai usor accesibil.Nodurile pot fi considerate orase, iar muchiile drumuri; grafurile orientate pot reprezente drumuri cu sens unic intre cladiri.

De asemenea, ne putem reprezenta traiectoria unei calatorii cu ajutorul unui lant al unui graf neorientat.

Grafurile mai pot arata legaturile dintre anuminte grupuri sau oameni; grafuri orientate pot arata transferul de informatii sau a unor bunuri.Un arbore genealogic este de asemena un graf neorientat.

Cablurile de inalta tensiune care pornesc dintr-o centrala pot fi si ele reprezentate cu usurinta cu ajutorul unui graf orientat, indicand si directia de deplasare a curentului. In acest caz centrala este un nod sursa. La fel se poate reprezenta si un sistem de canalizare, de incalzire sau reteaua de apa curenta.

Multitudinea cailor aeriene reprezinta grafuri. Nodurile sunt intersectiile (imaginare) si muchiile sunt rutele (imaginare). Noduri pot fi si aeroporturile.

Teoria grafurilor are numeroase apeluri in chimie, contribuind in mare masura la rezolvarea problemelor de numarare a grafurilor apartinand unor clase speciale. Teoria grafurilor este folosita in domenii variate: de la chimie la economie, de la studiul retelelor electrice la critica textelor de politica, devenind o disciplina majora.

Acum ca am aflat cat de folositoare sunt grafurile, ne punem intrebarea:

Ce sunt GRAFURILE?

Elemente teoretice-structura de tip GRAFGrafurile sunt structuri de date care se pot

implemente atat ca structuri de date alocate static cât şi alocate dinamic. Grafurile sunt utilizate în modelarea problemelor legate de activitati întâlnite în realitatea de zi cu zi. Structura unui graf reflectă structură unei probleme reale.

Grafurile sunt formate din puncte (numite noduri sau vârfuri - engleza = nodes / vertices) şi conexiuni între noduri (numite muchii – engleza edges).

Nod=componenta a grafului,si extremitati a muchiilor

Muchie=”drumul” dintre 2 noduri

Lant=o succesiune de 2 noduri cu proprietatea ca oricare 2 noduri consecutive din lant sunt adiacente. Definiţie Numim muchii adiacente două muchii cu o extremitate comună. Pentru exemplul de mai sus, muchiile [1,5] şi [5,4] sunt muchii adiacente pentru că au ca extremitate comună nodul 5.

Parcurgerea pe latime se efectueaza prin utilizarea structurii numita coada,avand grija ca un nod sa fie vizitat o singura data.

De exemplu, în figura de mai jos avem două grafuri A şi B, fiecare cu câte 5 noduri şi număr diferit de muchii.

Se numeşte graf neorientat, o pereche ordonată de multimi notată G = (V,E), unde V = {v1, v2, …, vn} este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri iar E = {e1,e2,…,en} este o mulţime de perechi neordonate de elemente din E numite muchii.

Se numeşte graf orientat o pereche ordonată de mulţimi G=(V,E), unde unde V = {v1, v2, …, vn} este o multime finită şi nevidă, numită mulţimea nodurilor sau vârfuri, iar E = {e1,e2,…,en} este o mulţime formată din perechi ordonate de elemente ale lui E, numită mulţimea arcelor.

Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al

pietonilor, „graful unui oraş” este neo-rientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele

străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noţiunea de graf orientat.

Problema

Un exemplu de graf din lumea reala reprezinta drumurile dintre orase. De exemplu, doresc sa aflu daca intre doua orase exista drum care le leaga. Luand doua orase la intamplare,vrem sa stim daca exista drum intre ele.

Despre problemaSe da o tara in care se afla m

noduri(orase). Muchiile reprezinta drumul dintre ele. Citind de la tastatura matricea de adiacenta a grafului si o insiruire de m noduri aflati daca exista drum de legatura intre ele. (exista un lant format din nodurile citite.) Sa se afiseze toate orasele folosind o metoda de parcurgere.

Modul de rezolvare al problemei

citim matricea de adiacenta si cele m noduri

verificam daca exista un lant format din cele m noduri

parcurgem graful folosind metoda pe latime

afisam rezultatul

Programul c++#include<iostream.h>

int a[50][50];

int main()

{int n,m,I,j,b[50],ok,prim,ultimo,start,x,y,v[100],c[100];

cout<<”n=”;cin>>n;

cout<<”m=”;cin>>m;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{cout<<”a[”<<i<<”][”<<j<<”]=”;

cin>>a[i][j];

a[j][i]=a[i][j];}

for(i=1;i<=m;i++)

{cout<<”b[”<<i<<”]=”;

cin>>b[i];}

ok=1;

for(i=1;i<m;i++)

{if(a[b[i]][b[i+1]]==0)

ok=0;

if(ok)

cout<<”Da”;

else

cout<<”Nu”;}

prim=1;

ultim=1;

cout<<”nodul de pornire”;

cin>>start;

for(i=1;i<n;i++)

for(j=i+1;j<=n;j++)

{cout<<”a[”<<i<<”]

[”<<j<<”]=”;

cin>>a[i][j];

a[j][i]=a[i][j];}

v[start]=1;

c[1]=start;

while(prim<=ultim)

{for(j=1;j<=n;j++)

if(a[c[prim]][j]==1 && v[j]==0)

{ultim++;

c[ultim]=j;

v[j]=1;}

prim++;}

for(i=1;i<=ultim;i++)

cout<<c[i]<<” ”;

}

Alte exemple de grafuri din viaţa reală

Intr-o fabrica sunt n muncitori .Intre acesti muncitori exista relatia de colegialitate.

a) Sa se reprezinte sub forma de graf muncitorii fabricii respective si relatiile dintre ei pentru n=6.

b) Ce fel de graf ati obtinut ?

Rezolvarea)Reprezentarea grafului.

Fiecare muncitor este coleg cu ceilalti.

b)Se obtine un graf complet.