Grafuri euleriene 

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m  muchii).  Lanţ eulerian = un lanţ simplu care conţine toate muchiile unui graf 

Lantul: L=[1.2.3.4.5.3.6.2.5.6] este lant eulerian Ciclu eulerian = un ciclu simplu care conţine toate muchiile grafului Ciclul: C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian  Graf eulerian = un graf  care conţine un ciclu eulerian. Condiţie necesară şi suficientă: Un graf este eulerian dacă şi numai dacă oricare vârf al său are gradul par.Observatie: graful poate fi eulerian si daca contine noduri izolate. Problema: fiind dat un graf fara noduri izolate sa se determine daca este eulerian. In caz afirmativ se vor afisa toate ciclurile euleriene care incep cu un nod nd citit.-         vom determina daca graful este conex-         vom determina daca fiecare nod are grad par-         vom genera toate ciclurile euleriene utilizand tehnica

backtracking. Astfel:o       primul nod va trebui sa fie ndo       un nou x=st[k], adaugat in stiva trebuie sa fie adiacent

cu anteriorul (y=st[k-1])o       muchia x-y nu trebuie sa mai fi fost adaugata inca

odatao       ultimul nod, care incheie ciclul, trebuie sa fie incident

cu primul O solutie: 

#include<fstream.h>#include<conio.h>int st[100];int k,nd; int a[10][10],viz[10],n,m; void df_r(int nod) //parcurgere in adancime{int k; cout<<nod<<" "; viz[nod]=1; for(k=1;k<=n;k++)  if(a[nod][k]&&!viz[k])     df_r(k);} int e_valid(){int x,y;if(k==1)   if(st[k]!=nd)       return 0;if(k>1) //sa existe muchie cu precedentul   {x=st[k];    y=st[k-1];    if(a[x][y]==0)        return 0;    } for(int i=1;i<=k-2;i++)    if((st[i]==x && st[i+1]==y) ||  (st[i]==y && st[i+1]==x))          return 0; //muchia a mai fost luata odata //ultima muchie sa fie incidenta cu primaif(k==m)   if(a[st[m]][st[1]]==0)          return 0; return 1;} void tipar(){for(int i=1;i<=m;i++)    cout<<st[i]<<"  "; cout<<st[1]; cout<<endl;

 } void back(){ k=1; while(k>0)    {if(st[k]<n)         {st[k]++;          if(e_valid())              if(k==m)                 tipar();              else{k++;                   st[k]=0;                   }            }     else           k--;}}   void main(){clrscr();int x,y;fstream f;//int a[10][10];// citire matrice din fisierf.open("matsim.txt",ios::in);if(f)   cout<<"ok";else   cout<<"error";f>>n>>m;for(int i=1;i<=m;i++)  {f>>x>>y;     a[x][y]=a[y][x]=1;     } cout<<"matricea de adiac "<<endl;  // afisare matricefor( i=1;i<=n;i++) {for(int j=1;j<=m;j++)  cout<<a[i][j]<<" ";  cout<<endl;  }  cout<<"nd="; //nodul de la care se porneste cin>>nd;

 df_r(nd); int s=0; for(i=1;i<=n;i++)     s+=viz[i];  //pentru a verifica daca graful este conex if(s!=n)    cout<<"graful nu e conex "; else    {int gasit=0;     cout<<endl<<"graful e conex!"<<endl;     for(i=1;i<=n;i++) //determin daca toate nodurile au gradele pare        {s=0;         for (int j=1;j<=n;j++)                 s+=a[i][j];         if(s%2!=0)              gasit=1;}         if(gasit)             cout<<"am noduri fara grade pare";         else             cout<<"toate nodurile au gradele pare deci graful e eulerian";             }         back();         getch();  }  O varianta mai eficienta de determinare a unui ciclu eulerian este urmatoarea: Fie graful din figura urmatoare: 

      

-se determina daca graful contine un ciclu eulerian (toate nodurile au grad par si este conex)-se retin gradele tuturor nodurilor in vectorul g. Acesta va retine:

g=[2,4,4,4,4,2]-ciclul se genereaza pas cu pas retinand nodurile intr-o lista gestionata de variabilele p si u (prima si ultima componenta)-se genereaza un ciclu pornind de la nodul 1 care se adauga in lista p (acesta va fi si u la inceput). In continuare se adauga noduri adiacente cu informatia retinuta de u si se continua astfel pana se ajunge iar la nodul 1. De fiecare data cand se adauga o muchie (u->info, i) la ciclu se micsoreaza gradul lui          u->info si lui i iar muchiile (u->info, i) si (i,u->info) se elimina.-acest prim ciclu se poate genera parcurgand nodurile grafului-dupa prima secventa se determina ciclul :

       

-         lista va retine : p={1, 2, 3, 1}  iar g devine : g=[0, 2, 2, 4, 4, 2]

-         in continuare se cauta un nou ciclu care sa porneasca de la un nod x din p si pt care g[x]>0. Primul astfel de nod gasit este : x=2. Acest nou ciclu este memorat de o noua lista gestinata de p1 si u1. Ciclul nou se cauta dupa acelasi principiu. Se obtine :

p1={2, 4, 3, 5, 2} iar g devine : g=[0,0,0,1,1,1] 

       

  

Noul ciclu se insereaza dupa x gasit (x=2, se insereaza lista p1 in lista p) si se obtine : p={1,2,4,3,5,2,3,1} -mai departe pe acelasi principiu se cauta x (x=4)iar urmatorul ciclu este p1={4, 5,6,4} si g ajunge la g={0,0,0,0,0,0}. Acesta se insereaza dupa 4 :Se obtine : p={1,2,4,5,6,4,3,5,2,3,1} 

       

O variabila k retine numarul muchiilor adaugate la ciclu si algoritmul continua pana k ajunge la m (numarul de muchii). O solutie de implementare este : #include<fstream.h>#include<conio.h>struct nod{int info;           nod *next;}; int a[20][20],viz[20];int g[20];int n,m,k; void df(int nod){viz[nod]=1;for(int k=1;k<=n;k++)    if(a[nod][k]==1&&viz[k]==0)             df(k);} void citire(){ int x,y;fstream f; //memorare graf in matrice de adiacentaf.open("euler.txt",ios::in);if(f)   cout<<"ok";

else   cout<<"eroare";cout<<endl;f>>n>>m;for(int i=1;i<=m;i++)    {f>>x>>y;    g[x]++; g[y]++;    a[x][y]=a[y][x]=1;    }}  int verific(){ for(int i=1;i<=n;i++)    if(g[i]%2==1)       return 0;df(1);for(i=1;i<=n;i++)   if(viz[i]==0)      return 0;return 1;}  void generezc1(nod*&p,nod*&u,int x){nod *q;q=new nod;q->info=x;p=u=q; do  { int gas=0;   for(int i=1;i<=n&&!gas;i++)        if(a[i][u->info]==1)            {g[u->info]--;            g[i]--;            k++;            a[i][u->info]=a[u->info][i]=0;            q=new nod;            q->info=i;            u->next=q;            u=q;            gas=1;}  }

while(p->info!=u->info);u->next=0;}  void afisare(nod *q) {while(q)      {cout<<q->info<<" ";       q=q->next;}  } int cauta(nod *&q){while(q)   {if(g[q->info])       return q->info;    q=q->next;   }return 0;} void main(){clrscr();citire();if(verific()==0)   cout<<"gf nu este eulerian!";else { cout<<"este eulerian!";nod *p=0,*u;cout<<endl;generezc1(p,u,1);cout<<endl;nod *p1=0,*u1;while(k<m)   {nod *q=p;    int x=cauta(q);    generezc1(p1,u1,x);    u1->next=q->next;    q->next=p1->next;   } afisare(p); }getch(); 

  }