grafuri orientate
DESCRIPTION
Grafuri orientate. Proiect realizat de Caramizoiu Vlad Colegiul National Ecaterina Teodoriu. Aplicatii ale grafurilor in viata reala - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/1.jpg)
Grafuri orientate
Proiect realizat de Caramizoiu VladColegiul National Ecaterina Teodoriu
![Page 2: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/2.jpg)
Aplicatii ale grafurilor in viata reala Sa presupunem ca esti in Targu-Jiu,este ora 7:45 si vrei sa ajung la
scoala inainte de ora de incepere a cursurilor ,aceasta fiind situata in partea opusa a orasului .Mai ai la dispozitie 15 minute astfel ca singura ta sansa este sa gaseasci drumul cel mai scurt.
![Page 3: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/3.jpg)
Intr-un moment de sclipire acesta iti dai seama ca reteaua stadala a orasului seaman cu un graf orientat si ca poti ulitiza un program C++ pentru a determina drumul minim.
Inainte de o continua povestea sa ne amintim cate ceva despre grafuri.
![Page 4: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/4.jpg)
Grafuri Orientate– •
![Page 5: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/5.jpg)
• •
![Page 6: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/6.jpg)
•
![Page 7: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/7.jpg)
Asadar trebuia sa realizezi un algoritm care sa calculeze drumul cel mai scurt de la tine de acasa pana la scoala la care inveti.(Daca nu stii realizezi un astfel de algoritm este probabil din cauza ca te jucai asphalt 8 in timp ce profesoara explica grafurile)
Sa presupunem ca fiecare starda(muchie) in functie de
lungimiea sa are un anumit cost.Un astfel de program consta in gasirea lantului de cost minim ce uneste cele 2 puncte .
Un graf caruia i s-a asociat o functie cost se numeste graf
ponderat.Functia cost asociata unai graf se foloseste pentru determinarea drumurilor de cost minim existente intre cele 2 noduri ale graficului.Pentru aceasta fiecarui graf i se asociaza o matrice numita matricea costurilor.Matricea costurilor are 2 variante in functie de scopul in care a fost definita.
![Page 8: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/8.jpg)
Pentru determinarea drumurilor de cost minim se defineste matrice astfel: -M(i,j)=0,daca i=j; - M(i,j)=c(cost),daca i!=j si exista arc de la i la j ; -M(i,j)=∞,daca i!=j si nu exista arc de i la j. Pentru determinarea costului minim intre 2 noduri (x si
y)se pleaca de la matricea initiala M si se transforma aceasta asemanator algoritmului de obtinere al matricei drumurilor alegand fiecare nod ca fiind nod intermediar intre alte 2 noduri
![Page 9: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/9.jpg)
Matricea drumurilor de cost minim se obtine cu algoritmul Roy-Floyd:
#include<fstream.h> ifstream f(“date.in”); ofstream g(“date.out”); int main() {f>>n>>m; for(i=1;i<=n;i++) for(f=1;j<=n;j++) if(i==j) a[i][j]=0; else a[i][j]=9999999;
![Page 10: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/10.jpg)
for(i=1;i<=n;i++) {f>>x>>y>>c; a[x][y]=c;} for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j]; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) g<< a[i][j]<<’ ‘; g<<’n’;}}
![Page 11: Grafuri orientate](https://reader037.vdocumente.com/reader037/viewer/2022100208/56815e3c550346895dcca304/html5/thumbnails/11.jpg)
In final probabil nu vei reusii sa faci un program functional ,vei intarzia la scoala ajungand astfel la 10 absente si drept urmare media ta la purtare va avea de suferit de suferit.
Morala: Fii atent la ora de informatica ,nu stii niciodata
cand o sa iti trebuiasca in viata.