Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Grafurile în viaţa de zi cu zi

No description
by

Razvan Burciu

on 16 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Grafurile în viaţa de zi cu zi

Proiect realizat de Răzvan Burciu Grafurile în viața de zi cu zi Grafurile în viaţa de zi cu zi Un bun exemplu de graf cu aplicativitate în viaţa de zi cu zi, ar putea fi rețeaua INTRANET a unei companii (rețeaua locală de calculatoare a unei companii).

În cadrul unei astfel de rețele, toate calculatoarele, imprimantele, scanner-ele etc. sunt conectate, formând o conexiune de tip LAN.

Avantajele unei astfel de rețele sunt:
- posibilitatea de a transmite fișiere și informații
foarte rapid între elementele rețelei
-asigurarea unei securități interne a
informațiilor și fișierelor O problema practică Să presupunem că avem o rețea INTRANET a unei
firme. Fiecare componentă a rețelei reprezintă un nod al unui graf neorientat cu n varfuri, iar legăturile dintre acestea reprezintă muchiile grafului.
Citind de la tastatură matricea de adiacență, afișati în fișierul rețea.txt componenta cu cele mai multe legături din cadrul rețelei (componenta server care leaga toate celelalte componente ale rețelei), cât și toate componentele rețelei, parcurgând graful, începând cu elementul k, citit de la tastatură. Elemente teoretice Cunoașterea noțiunilor de:
graf neorientat, nod, muchie, gradul unui nod, matricea de adiacență a unui graf Numim graf neorientat o pereche de mulţimi G=(V, E), unde V este o mulţime finită nevidă de elemente numite noduri, iar E o mulţime de perechi neordonate din V, numite muchii. Definiţia unui graf Metode de parcurgere a unui graf Parcurgerea în lăţime (Breadth First BF)

Parcurgerea în adâncime (Depth First DF) Nod = element al mulţimii V, unde G=(V, E) este un graf neorientat.
Muchie = element al mulţimii E ce descrie o relaţie existentă între două noduri din V, unde G=(V, E) este un graf neorientat Parcurgerea în lăţime (BF)



Spunem că 2 noduri sunt adiacente dacă există o muchie care le leagă.
Spunem că o muchie este incidentă cu un nod, dacă nodul respectiv este o extremitate a muchiei.



Gradul unui nod V, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numărul de muchii incidente cu nodul respectiv) Gradul unui nod Parcurgerea în lăţime începe cu vârful iniţial, i, denumit şi vârful de start. Acesta se consideră vizitat.

Se vizitează în ordine toţi vecinii nevizitaţi ai vârfului de start (j1,j2,...,jk).

Apoi se vizitează, în ordine, toţi vecinii nevizitaţi ai nodului j1, apoi j2,... şi aşa mai departe, până au fost vizitate toate nodurile accesibile. -considerăm vârful de start ca fiind 1, vizitat
-afişăm în ordine vecinii săi: 2 4 6
-afişăm vecinii nevizitaţi ai nodului 2: 3 5
-nodul 3 nu are vecini nevizitaţi, nici 5
-nodul 4 nu are vecini nevizitaţi
-nodul 6 nu are vecini nevizitaţi Soluţia: 1 2 4 6 3 5 Parcurgerea în adâncime (DF) Parcurgerea în lăţime începe cu vârful iniţial, i, denumit şi vârful de start. Acesta se consideră vizitat.

Se vizitează primul vecin nevizitat al vârfului de start.

Apoi se vizitează primul dintre nodurile adiacente cu acesta (nevizitat încă) apoi următorul nod adiacent nevizitat, în adâncime, şi aşa mai departe, până au fost vizitate toate nodurile accesibile. -considerăm vârful de start ca fiind 1, vizitat
-afişăm primul vecin nevizitat al lui: 2
-afişăm vecinul nevizitat al nodului 2: 3
-continuăm până nu mai avem noduri nevizitate
-ne întoarcem la nodul 1, şi afişăm următorul său vecin nevizitat: 6
-nodul 6 nu are vecini vevizitaţi Soluţia: 1 2 3 4 5 6
-citim matricea de adiacență a grafului, citind elementele de deasupra diagonalei principale
-identificăm componenta server a rețelei care are gradul egal cu numărul de componente -1
-parcurgem graful folosind una din metodele de parcurgere menționate
-afișăm rezultatele în fișier Modalitate de rezolvare Rețea intranet #include<iostream.h>
#include<fstream.h>
int a[50][50],c[50],v[50];
int main(){
int n,i,j,k,prim,ultim,start;
cout<<"Numarul de componente ale retelei: ";
cin>>n;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++){
cin>>a[i][j];
a[j][i]=a[i][j];
} fstream fout("retea.txt",ios::out);
int s;
for(i=1;i<=n;i++){
s=0;
for(j=1;j<=n;j++)s+=a[i][j];
if(s==n-1)fout<<"Componenta server este componenta "<<i<<" si are "<<s<<" legaturi"<<endl;
} cout<<"Componenta de la care incepe parcurgerea: "<<endl;
cin>>k;
prim=1;ultim=1;
start=k;
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<=n;i++)
fout<<c[i]<<" ";
} Proiect realizat de Răzvan Burciu,
Profesor coordonator: Șandor Nicoleta
Full transcript