Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Definiţie: Se numeşte ciclu hamiltonian un ciclu elementar care trece prin toate vârfurile grafului. Un graf care admite un ciclu hamiltonian se numeşte graf hamiltonian. Fie G = (X,U) un graf neorientat şi un lanţ elementar care trece prin toate nodurile grafului [x0,x1, …, xn]. Dacă d(x1) + d(xn)≥n atunci graful este hamiltonian. Fie G … Read more
Graf eulerian #include<fstream.h>#include<conio.h>struct nod{int nd;nod *adr_urm;};int a[10][10],s[10],n;nod *lista, *indice; void citire(char graf[10],int a[10][10],int& n){int i,j;fstream f(graf,ios::in);f>>n;while (f>>i>>j) a[i][j]=a[j][i]=1;f.close();} void ciclu(nod* v){int nodul;nod *nod_baza,*nod_gasit,*nod_urm;nod_urm=v->adr_urm;nod_baza=v;do{ nodul=1;while (a[nod_baza->nd][nodul]==0) nodul++;a[nod_baza->nd][nodul]=0;a[nodul][nod_baza->nd]=0;nod_gasit=new nod;nod_gasit->nd=nodul;nod_gasit->adr_urm=0;nod_baza->adr_urm=nod_gasit;nod_baza=nod_gasit;}while (nod_gasit->nd!=v->nd);nod_baza->adr_urm=nod_urm;} int adauga(){int i,gasit=0;indice=lista;while(indice && !gasit){for(i=1;i<=n;i++)if (a[indice->nd][i]==1) gasit=1;if (!gasit) indice=indice->adr_urm;}if(indice){ciclu(indice);return 1;}else return 0;} int grade_pare(){int i=1,j,s,gasit=0;while ((i<=n) && !gasit ){s=0;for(j=1;j<=n;j++) s+=a[i][j];if (s%2) gasit=1;i++;}return !gasit;} void df(int nod){int k;s[nod]=1;for(k=1;k<=n;k++)if … Read more