Î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, pentru fiecare vârf al grafului, lista vecinilor săi. Date de intrare Fişierul de intrare listavecini.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între … Read more
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}