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 nd
o
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 odata
o
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 prima
if(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 fisier
f.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 matrice
for( 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 adiacenta
f.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();
}