Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului. Date de intrare Fiecare dintre liniile fișierului adiacenta1.in conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Date de ieşire Fişierul de ieşire adiacenta1.out va conţine n linii; pe fiecare dintre ele … Read more
Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului. Date de intrare Fişierul de intrare adiacenta.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele m linii conține câte o pereche de numere i … Read more
Definiţie: Se numeşte lanţ L = [x0, x1, …, xn]o succesiune de vârfuri cu proprietatea că oricaredouă vârfuri consecutive sunt adiacente.Vârfurile x0 şi xn se numesc extremităţile lanţului. Numărul n se numeşte lungimea lanţului şieste numărul de muchii din care este format.Lanţul care conţine numai vârfuri distincte, două câte două, este lanţ elementar.Lanţul care conţine … Read more
Definitie:Fie G=(V, M) un graf neorientat. Se numeşte subgraf al grafului G, graful neorientat G1=(V1,M1) unde V1⊆ V iar M1 contine toate muchiile din M care au extremitătile în V1. Exemplu:Fie graful neorientat: G=(V, M) unde: V={ 1,2,3,4} si M={[1,2], [2,3], [1,4]} reprezentat grafic astfel: Un exemplu de subgraf al grafului G este graful neorientat:G1=(V1 … Read more
Definitie.Fie G=(V, M) un graf neorientat. Se numeşte graf partial, al grafului G, graful neorientat G1=(V, M1) unde M1 ⊆ M. Concluzie:Un graf partial al unui graf neorientat G=(V, M) are aceeaşi multime de vârfuri ca şi G iar multimea muchiilor este o submultime a lui M sau chiar M. Exemplu: Fie graful neorientat: G=(V, … Read more
Definiţie: Se numeşte graf neorientat o pereche ordonată de mulţimi G=(X, U), unde: X = {x1, x2, x3, …, xn} este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime finită de perechi neordonate de forma (xi, xj), unde i≠j şi xi, xj∈X, numite muchii. O muchie uneşte două … Read more
Sa se parcurga in adancime DF un graf orientat. Graful este dat prin matricea de adiacenta. #include<fstream.h>#include<iostream.h>int v[20],a[20][20],n;void citire(){int i,j;fstream f(“matrice.txt”,ios::in);f>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)f>>a[i][j];}void df(int nod){int k;cout<<nod<<” “;v[nod]=1;for(k=1;k<=n;k++)if((a[nod][k]==1) && (v[k]==0))df(k);}void main(){citire();df(1);} {joscommentenable}
Descompunerea in componente tare conexe a unui graf orientat, dat prin matricea de adiacenta Matricea de adiacenta se citeste dintr-un fisier text #include <fstream.h>int s[20],p[20],a[20][20],n,nr,i,j;void df1(int nod){int k;s[nod]=nr;for(k=1;k<=n;k++) if ((a[nod][k]==1) && (s[k]==0)) df1(k);}void df2(int nod){int k;p[nod]=nr;for(k=1;k<=n;k++) if((a[k][nod]==1) && (p[k]==0)) df2(k);}void main(){fstream f(“grafo.txt”,ios::in);f>>n;while(f>>i>>j) a[i][j]=1;f.close();nr=1;for (i=1;i<=n;i++) if (s[i]==0) { s[i]=nr; df1(i);df2(i); for(j=1;j<=n;j++) if (s[j]!=p[j]) s[j]=p[j]=0; nr++; }for(i=1;i<=n;i++){cout<<“componenta … Read more
Descompunerea in componente conexe a unui graf neorientat, dat prin matricea de adiacenta #include<fstream.h>int s[20],a[20][20],n,i,j,k; void df(int nod){int k;cout<<nod<<” “;s[nod]=1;for(k=1;k<=n;k++) if((a[nod][k]=1) && (s[k]==0)) df(k);} void main(){fstream f(“graf.txt”,ios::in);f>>n;while(f>>i>>j) a[i][j]=1;f.close();k=1;for(i=1;i<=n;i++) if(s[i]==0) { cout<<“componenta “<<k<<endl; df(i); cout<<endl; k++; }} {joscommentenable}
Graf orientat tare conex #include<fstream.h>#include<conio.h>int s[50],a[50][50],n,suc[50],pred[50],i,j;void citire(char fis[20],int a[50][50],int&n){ fstream f(fis,ios::in); int i,j; f>>n; while(f>>i>>j) a[i][j]=1; f.close();} void df1 (int nod){ int k; suc[nod]=i; for (k=1;k<=n;k++) if ((a[nod][k]==1) && (suc[k]==0)) df1(k);}void df2(int nod){ int k; pred[nod]=i; for (k=1;k<=n;k++) if((a[k][nod]==1)&&(pred[k]==0)) df2(k);}void main(){citire(“fis.txt”,a,n);cout<<“nodul de pornire:”;cin>>i;suc[i]=pred[i]=i;df1(i);df2(i);for(j=1;j<=n;j++)if((suc[j]==pred[j])&&(suc[j]==i))cout<<j<<” “;getch();} {joscommentenable}