Grafuri hamiltoniene si grafuri euleriene
Definitie
Se numeste ciclu hamiltonian un ciclu elementar care contine toate varfurile grafului.
Definitie
Un graf se numeste hamiltonian daca are cel putin un ciclu hamiltonian.
TEOREMA
Fie G=(X,U) un graf. Daca gradul fiecarui varf este >=n/2 atunci graful este hamiltonian.
Observație: Conditia din teorema este necesara, dar nu si suficienta.
Aplicatie:
Ciclurile hamiltoniene sunt legate de problema comis-voiajorului care pleaca dintr-un oras si trebuie sa treaca o singura data prin celelalte orase si sa se intoarca de unde a plecat.
Problema:
Fiind dat un graf neorientat memorat prin matricea de adiacente sa se determine daca graful este Hamiltonian . In caz afirmativ sa se afiseze ul ciclu Hamiltonian altfel se va afisa un mesaj.
Pentru a rezolva problema vom utiliza tehnica backtracking. Vom incarca in stiva noduri distincte si adiacente, astfel incat pornind de la problema clasica de backtracking a permutarilor vom testa valoarea de pe nivelul k astfel:
· Sa fie un nod adiacent cu precedentul adaugat. E necesar ca: a[st[k-1]][st[k]]=1, in caz contrar se returneaza 0
· Nodul adaugat sa nu se regaseasca pe nivelurile anterioare . Trebuie ca st[k]¹st[i] unde iÎ{1,2…k-1}, in caz contrar se returneaza 0
· Pentru a se incheia ciclul este necesar ca primul si ultimul nod sa fie adiacente. Adica:
a[st[1]][st[n]]=1, in caz contrar se returneaza 0
#include<fstream.h>
#include<conio.h>
#include<stdio.h>
int st[100],n,m,k,a[20][20];
int ns;
//k este este nivelul din stiva (indexul – vetorul solutie),curent
int e_valid()
{if(k>1)
if(!a[st[k-1]][st[k]])
return 0;
else
for(int i=1;i<=k-1;i++)//parcurg nivelurile anterioarenivelului curent
if(st[i]==st[k])
return 0;
if(k==n)
if(!a[st[1]][st[k]])
return 0;
return 1;
}
void afisare()
{for(int i=1;i<=n;i++)
cout<<st[i]<<” „;
cout<<st[1];
k=0; //determina iesirea la prima solutie
ns++;
}
void back()
{k=1; //pe primul nivel initial
while(k>0)//cand k va descreste la 0 algoritmul se incheie
if(st[k]<n)
{st[k]++;
if(e_valid())//daca elementul incarcat este valid
if(k==n)//verific daca am ajuns la solutia completa.
afisare();
else //daca nu am solutia completa urc in stiva (maresc vectorul, adica pe k)
{k++;
st[k]=0;}
}
else
k–;
}
void main()
{clrscr();
fstream f;
f.open(„ham.in”,ios::in);
int u,v;
if(f)
cout<<„ok!”;
else
cout<<„eroare”;
cout<<endl;
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>u>>v;
a[u][v]=a[v][u]=1;
}
cout<<„matricea de adiac „<<endl; // afisare matrice de adiacenta
for( i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
cout<<a[i][j]<<” „;
cout<<endl;
}
back();
if(ns==0)
cout<<”nu exista solutii”;
getch();
}
Definitie
Un ciclu se numeste eulerian daca treceo singura data prin toate muchiile.
Definitie
Un graf se numeste eulerian daca are un ciclu eulerian.
TEOREMA
Un graf fara varfuri izolate se numeste eulerian daca si numai daca este conex si gradul fiecarui varf este par.
Observație
Dintre grafurile complete sunt euleriene cele cu numar impar de varfuri.
Definitie
O componenta conexa este un subgraf conexmaximal cu aceasta proprietate.
Definitie
O componenta conexa a unui graf G=(X,U) este un subgraf S=(Y,Z) cu proprietatea ca nu exista un lant care sa uneasca un varf din Y cu un varf din X-Y.
Observație
Fiecare varf izolat constituie o componenta conexa.
Codul sursa: Determinarea componentelor conexe
#include<iostream.h>
int a[20][20],cc[30];
int n,ncc,i,j,v; // ncc=nr. de componente conexe
void df(int v)
{
int i;
cc[v]=ncc;
for(i=1;i<=n;i++)
if( (a[v][i]==1) && (cc[i]==0) )
df(i);
}
int main(void)
{
cout<<„Dati numarul de varfuri n = „; cin>>n;
cout<<„Matricea de adiacenta „<<endl;
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
{
cout<<„a[„<<i<<„,”<<j<<„]= „;
cin>>a[i][j];
a[j][i]=a[i][j];
}
ncc=0;
for(i=1;i<=n;i++) cc[i]=0;
for(i=1;i<=n;i++)
if (cc[i]==0)
{
ncc=ncc+1;
df(i);
}
for(i=1;i<=ncc;i++) // ncc = nr. de comp. conexe
{
cout<<„componenta „<<i<<” „;
for(j=1;j<=n;j++)
if(cc[j]==i)
cout<<j<<” „;
cout<<endl;
}
}
Considerăm ca exemplu graful de mai jos, cu n=8 vârfuri
2 6
3
1 7
5 4 8
Soluţie
În funcţia principală main se citesc: numărul de vârfuri n , numărul de muchii m , precum şi cele m perechi de numere ce reprezintă extremităţile muchiilor grafului.
Elementele matricei de adiacenţă se vor tipări pe monitor. Tot în acest modul vom apela funcţia conex ().
În funcţia conex() verificăm dacă graful este conex situaţie în care vom apela funcţia grad(), iar dacă graful nu este conex vom afişa un mesaj „graful nu este eulerian”.
Funcţia grad() verifică dacă gradele tuturor vârfurilor sunt numere pare.
Programul aferent este:
#include<stdio.h>
#include<conio.h>
int a[20][20],n,m,x,y,i,j;
void conex();
void grad();
void main()
{
clrscr();
printf(„Dati nr de muchii:”);
scanf(„%d”,&m);
printf(„Dati nr de varfuri:”);
scanf(„%d”,&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=m;i++)
{do{
printf(„\n Dati muchia nr %d: „,i);
scanf(„%d%d”,&x,&y);
} while(x==y||x<1||x>n||y<1||y>n);
a[x][y]=1;
a[y][x]=1;
}
printf(„\nMatricea de adiacenta corespunzatoare este:\n\n”);
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
printf(„%2d”,a[i][j]);
printf(„\n”);
}
conex();
getch();
}
void conex()
{
int start,viz[20],c[20],pi,ps,z;
printf(„\nDati varful start:”);
scanf(„%d”,&start);
for(i=1;i<=n;i++)
{viz[i]=0;
c[i]=0;
}
ps=1;
pi=1;
c[pi]=start;
viz[start]=1;
while(ps<=pi)
{
z=c[ps];
for(i=1;i<=n;i++)
if(a[i][z]==1&&viz[i]==0)
{pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
if(pi==n)
grad();
else
printf(„\nGraful nu este eulerian”);
}
void grad()
{
int grad,k;
k=0;
for(i=1;i<=n;i++)
{ grad=0;
for(j=1;j<=n;j++)
if(a[i][j])
grad++;
if(grad%2!=0)
k=1;
}
if(k==0)
printf(„\nGraful este eulerian”);
else printf(„\nGraful nu este eulerian”);
}
*Să se afişeze matricea de adiacentă a unui graf neorientat cu n noduri şi m muchii.
#include<iostream>
using namespace std;
int mat[10][10],n,m;
void citire()
{int a,b,i,m;
for(i=1;i<=m;i++)
{cout<<„Dati muchia”<<i<<„=”;
cin>>a>>b;
mat[a][b]=mat[b][a]=1;
}
}
void afisare()
{int i,j;
cout<<„Matricea de adiacenta”;
cout<<endl;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
cout<<mat[i][j]<<” „;
cout<<endl;
}
}
int main()
{int i,j;
cout<<„n=”;cin>>n;
cout<<„m=”;cin>>m;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
mat[i][j]=0;
citire();
afisare();
}
Grafuri neorientate. Probleme propuse
- Fie un graf neorientat memorat prin matricea de adiacente si o succesiune de k noduri. Sa se determine daca succesiunea citita este un lant din graf
- Din fisierele mat1.in si mat2.in se citesc doua matrici patratice associate grafurilor g1 si g2. Sa se deremine daca g2 este graf partial pentru g1
- Fie o harta cu n orase. Cele n orase se citesc din fisier. Intre cele n orase exista m drumuri. Se cunosc distantele celor n drumuri.
- Sa se determine daca orasul x si orasul y sunt vecine
- Sa se afiseze lungimile tuturor localitatilor intre care exista drum direct
- Sa se determine lungimea minima a drumului dintre doua localitati citite de la tastatura
- La o receptie sunt invitate n personae. Se cunosc numele celor n persoane . Intre anumite persoane exista relatii de colaborare. Sa se determine daca se pot dispune cele n personae la o masa rotunda astfel incat intre oricare doua personae alaturate sa existe relatii. Se citesc : numele persoanelor si cele m relatiile sub forma de perechi de nume
- Un eschimos locuieste la iglul cu numarul z. El are o harta pe care sunt marcate iglu-urile din zona (numerotate de la 1 la n) si distantele dintre acestea. Stiind ca din cauza frigului eschimosul nu poate sa parcurga o distanta mai mare de 20 km fara oprire, afisati o varianta de a ajunge la prietenul lui care locuieste la iglul cu numarul w, eventual cea mai scurta varianta care indeplineste cerinta data. Cati kilometri a parcurs eschimosul?
- Un graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua multimi A si B astfel incat oricare doua varfuri din aceeasi multime sa nu fie adiacente. Sa se scrie un program care verifica daca un graf este bipartit si in caz afirmativ sa se tipareasca multimile A si B
- Problema colorarii unei harti. Se citesc 4 culori (siruri de caractere) si denumirile a n tari (siruri de caractere) . Sa se coloreze harta astfel incat sa nu existe doua tari alaturate avand aceeasi culoare. Se va afisa o solutie : tara-culoare, tare-culoare etc.
- Sa se coloreze un graf astfel incat oricare doua muchii incidente cu acelasi nod sa fie colorate diferit. Care este numarul minim de culori necesar.
- O pestera are n incaperi, fiecare situata la o adancime h. Configuratia pesterii este data de cele m culoare de acces intre camerele pesterii (culoarele sunt date ca extremitati). In incaperea s exista un izvor de apa sulfuroasa. Se dau n, m, cele m culoare (ca perechi x-y), s si adancimile h ale camerelor. Determinati incaperile inundate si culoarele umezite.
- Fie un graf neorientat. Sa se determine daca graful contine cicluri.
informatica.cnet 