Grafuri Orientate
Definitie:Se numeste graf orientat (G) o pereche ordonata de multimi (X,U),unde X este o multime finita si nevida de elemente ,iar U o multime de perechi ordonate formate cu elemente distincte din multimea X.
X={1,2,3,4,5}
U={(1,2),(1,3),(2,5),(4,2),(4,5)}
Matricea de adiacenta asociata acestui graf orientat este patratica si nesimetrica.
Dimensiunea matricii de adiacenta este data de multimea varfurilor.
A[i][j]= 
Terminologie :
Pentru arcul (x,y),x se numeste extremitate initiala ,iar y se numeste extremitate finala.
Se numeste succesor al varfului x orice varf in care ajunge un arc care pleaca din varful x.
Se numeste predecesor al varfului x orice varf in care intra un arc care pleaca din nodul x.
Gradul unui nod este format din:
-grad extern -grad intern
Gradul extern este egal cu numarul arcelor care au ca extremitate initiala varful x(este numarul arcelor care ies din varful x).
Gradul intern este egal cu numarul arcelor care au ca extremitate finala varful x.
(pe linie)(pe coloana)
Un varf izolat este un varf care are gradul intern egal cu extern egal cu zero.
Multimea (gama plus) si (gama minus) Multimea pentru varful x este egala cu multimea varfurilor care reprezinta succesorii varfului x.
Multimea reprezinta multimea varfurilor care sunt predecesoare varfului x.
Multimea (omega plus) si (omega minus) Multimea reprezinta multimea muchilor care au ca extremitate initiala varful x.
Multimea reprezinta multimea muchilor care au ca extremitate finala varful x
.
Un nod terminal este un nod care are suma gradelor externe si interne egala cu 1.
Exemplu :
1.Sa se afiseze multimea omega minus pentru un varf k citit de la tastaura,pentru un graf orientat cu n varfuri.
1.Sa se afiseze multimea omega minus pentru un varf k citit de la tastaura,pentru un graf orientat cu n varfuri.
cout<< ‘’{‘’ ;
for(i=1;i<=n ;i++)
if(a[i][k]==1)
cout<<’’(‘’<<<’’,’’<<<’’)’’;
cout<<’’}’’;
Teoreme
1.Numarul total de grafuri orientate care se pot forma cu n noduri este.2.Intr-un graf orientat cu n varfuri ,suma gradelor interne ale tuturor nodurilor este egala cu suma gradelor externe ale tuturor nodurilor si cu numarul de arce.
Suma gradelor interne ale tuturor varfurilor este egala cu suma gradelor externe si este egala cu numarul de arce.
Matricea varfuri-arce
b[i][j]- este o matrice care are n linii si m coloane,unde n este egal cu numarul de varfuri si m este egal cu numarul de muchii.
b[i][j]= b[i][j]=
Matricea de adiacenta
for(j=1;j<=m;j++)
for(i=1;i<=n;i++)
{if(b[i][j]==-1)
ef=i; ef-extremitatea finala
if(b[i][j]==1)
ei=i; ei-extremitatea initiala
a[ei][ef]=1;
}
Exemplu:
1.Sa se scrie o secventa de program care verifica in matricea varfuri-arce daca exista varfuri care au gradul intern egal cu gradul extern.
ok=0;
for(i=1;i<=n;i++)
{s=0;
for(j=1;j<=m;j++)
s=s+b[i][j];
if(s==0)
ok=1;}
if(ok==1)
cout<<”Grade egale”;
else
cout<<”Nu avem varfuri cu grade egale’’ ;
Lant,drum in grafurile orientate
Def :Numim lant intr-un graf orientat o succesiune de varfuri cu proprietatea ca oricare 2 varfuri consecutive sunt adiacente.
5,1,2,4,3-lant elementar
3,4,2,5-lant elementar
3,4,2,5,1,2-lant neelementar
1,2,3-nu este lant
Numim drum o succesiune de noduri cu proprietatea ca intre oricare 2 varfuri succesive exista un arc.
5,1,2,4,3-nu este drum
3,4,2,5-nu este drum (deoarece intre 3 si 4 nu avem arc,doar intre 4 si 3)
2,1,4,3-drum elementar
Matricea drumurilor(md)
md[i][j]=
md=
Daca diagonala principala are toate elementele nule inseamna ca graful orientat nu contine nici un circuit.
Daca exista un element nenul pe diagonala principala atunci inseamna ca exista circuit care pleaca din varful i(i=j).
for(i=1 ;i<=n ;i++)
for(j=1 ;j<=n ;j++)
md[i][j]==a[i][j] ;
for(k=1 ;i<=n ;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(md[i][j]==0 && i!=k && j!=k)
md[i][j]=md[i][k]*md[k][j];
Graf Conex
Un graf G se numeste conex daca intre oricare 2 varfuri diferite exista un lant care sa le uneasca.
Componenta conexa a unui graf orientat
Daca avem un graf G care nu este conex,se numeste componenta conexa a grafului G un subgraf al sau care este conex.
Obs :Un graf conex are o singura componenta conexa.
Graful are 2 componente conexe.
Graf tare conex
Def :Un graf orientat G se numeste tare conex daca indeplineste urmatoarea proprietate :pentru oricare 2 varfuri x,y(x !=y) exista drum de la varful x la varful y si un alt drum de la varful y la varful x.
Daca un graf orientat G nu este tare conex se numeste componenta tare conexa a grafului un subgraf tare conex al sau.
GT1 GT2
GT1-este un graf conex
Componenta tare conexa :{1,3,7},{4,5},{2},{6}
GT2-este un graf tare conex
GT4
GT4-graful nu este conex
Componentele conexe sunt formate din submultimile ;{1,2},{3,4,5,8},{6,7,9}
Teoreme
1.Daca un graf nu contine un lant intre 2 noduri x si y atunci contine un lant elementar intre nodurile x si y.
2.Daca un graf contine un drum intre 2 noduri x si y atunci contine un drum elementar intre nodurile x si y.
3.Daca un graf contine un ciclu atunci contine si un ciclu elementar.
4.Daca un graf contine un circuit atunci contine si un circuit elementar.
Teoreme :
1.Numarul minim de muchii necesare ca pentru un graf neorientat sa fie conex este n-1.
2.Un graf conex cu n noduri si n-1 muchii este aciclic si maximal cu aceasta proprietate.
3.Daca un graf neorientat conex are n noduri si m muchii ,numarul de muchii care trebuie eliminate pentru a obtine un graf partial conex aciclic este m-n+1.
4.Daca un graf are n noduri,m muchii si p componente conexe, numarul de muchii care trebuie eliminate pentru a obtine un graf partial aciclic(arbore) este egal cu m-n+p.
5.Pentru a obtine dintr-un graf neorientat conex 2 componente conexe,numarul minim de muchii care trebuie eliminate este cel mult egal cu gradul minim din graf.
6.Numarul maxim de muchii dintr-un graf neorientat cu n noduri si p componente conexe este (n-p)*(n-p+1)/2.
Parcurgerea in latime
p=u=1 ;
for(i=1;i<=n ;i++)
vix[i]=0;
c[p]=1;viz[1]=1;
while(p<=u)
{x=c[p]; p++;
for(y=1;y<=n;y++)
if(a[x][y]==1 && viz[y]=0)
{u++;
c[u]=y;
viz[y]=1;}}
Grafuri Speciale
Def;Graful G se numeste graf bipartit daca exista 2 multimi nevide de noduri A si B care au urmatoarele proprietati:AUB=X si A∩B=nultimea vida si orice muchie (arc) din multimea de noduri U are o extremitate in multimea de noduri A si o alta extremitate in multimea de noduri B.
Def ;Graful bipartit G se numeste graf bipartit complet daca pentru orice nod xi care apartine lui A si orice nod xj care aprtine lui B exista o muchie (un arc ) formata din cele 2 noduri care apartin multimii U([xi,xj] € U)
Exemplu :
GT1 GT2
Graful GT1 este graf bipartit
A={1,3,5} B={2,4,6,7}
Graful GT2 este bipartit complet
A={1,2} B={3,6,7}
Def :Numim lant hamiltonian un lant elementar ce contine toate nodurile grafului.
Def :Numim ciclu hamiltonian un ciclu elementar ce contine toate nodurile grafului.
Def :Un graf ce contine un ciclu hamiltonian se numeste graf hamiltonian.
Def :Numim ciclu eulerian un ciclu ce contine toate muchiile grafului.
Def :Un graf ce contine un ciclu eulerian se numeste graf eulerian.
Def :Un graf orientat in care ,intre oricare 2 noduri exista un singur arc si numai unul se numeste graf turneu.
Exemplu :
GT1 GT2
GT3
Graful Gt1 este hamiltonian dar nu este eulerian.
Graful GT2 este hamiltonian si eulerian.
Graful GT3 este eulerian dar nu este si hamiltonian.
Teoreme :
1.Un graf cu mai mult de 2 noduri este hamiltonian daca gradul fiecarui nod este >=n/2.
2.Un graf ce nu contine grafuri izolate este eulerian daca si numai daca este conex si gradele tuturor nodurilor sunt pare.
3.Numarul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1) !/2.
4.Orice graf turneu contine un drum elementar care trece prin toate nodurile grafului.
5.Pentru orice graf turneu ,exista un nod x,astfel incat toate nodurile y !=x sunt accesibile din x pe un drum care contine un arc sau doua arce.