Grafuri

GRAFURI

1) Grafuri Neorientate

Se numeste graf neorientat , perechea G=(X,U) , unde X este multime finita si nevida numita multimea varfurior , iar U este
formata din perechi neordonate de elemente din X si poarta denumirea de multimea muchiilor.

Numarul de grafuri neorientate care se pot construi cu n varfuri este 2^(Combinari de n luate cate 2)

Definim gradul unui varf x ca fiind numarul de muchii incidente in varful x.

Se numeste varf izolat , un varf de gradul 0.

Se numeste varf terminal , un varf de gradul 1.

Intr-un graf neorientat , suma gradelor varfurilor este egala cu 2*m ( nr de muchii )

Se numeste graf partial al grafului G , graful G1=(X,U1) cu U1 inclus inŠ‚ U

Nr de grafuri partiale a unui graf cu m muchii este 2^m

Se numeste subgraf al grafului G , graful G1=(X1,U1) unde X1 inclus inŠ‚ X , iar U1 este formata din acele muchii din U care au ambele
extremitati in multimea X1.

Nr de subgrafuri ale unui graf cu n varfuri este 2^n - 1

Se numeste graf complet , un graf in care oricare 2 varfuri sunt adiacente ( Gradul oricarui varf este n-1 ) ( nr de muchii este
 (n*(n-1)/2)

Se numeste graf nul , un graf in care toate varfurile au gradul 0.

Se numeste graf regulat , un graf in care toate varfurile au acelasi grad.

Metode de reprezentare : 1 ) Lista de muchii :
fiecare muchie va fi memorata intr-un vector v cu elemente de tip struct, struct muchie {int e1,e2;};
                         2 ) Matricea de adiacenta :
vom folosi o matrice de adiacenta ( n linii n coloane ) , a[i][j]=1 daca exista muchie de la i la j si 0 altfel.
diagonala principala a matricei de adiacenta are peste tot valoarea 0 , iar matricea este simetrica fata de diagonala principala.
                         3 ) Matricea de incidenta :
 vom folosi o matrice de incidenta , care va avea n linii si m coloane , B[i][j] = 1 daca muchia j este incidenta in varful i si 0 altfel.
                         4 ) Listele de adiacenta :
pentru a memora lista de adiacenta a unui graf , vom folosi o matrice cu n linii , fiecare linie memorand vecinii varfului corespunzator linieie respective

LANTURI / CICLURI

Se numeste lant in graful G=(X,U) , succesiunea de varfuri L=[x1,x2,..,xk] cu xi apartine lui x si i luand valori de la 1 la k , avand proprietatea ca intre oricare doua varfuri consecutive xi,xi+1 exista muchie.

Lungimea lantului este data de numarul de muchii care compun lantul. ( nr de noduri - 1 )

Se numeste lant elementar , un lant cu varfurile distincte.

Se numeste lant simplu , un lant in care muchiile sunt distincte

Se numeste ciclu , un lant simplu in care extremitatea initiala coincide cu extremitatea finala

Se numeste ciclu elementar , un ciclu in care varfurile sunt distincte cu exceptia primului si ultimului varf.


PARCURGEREA GRAFURILOR

1) Parcurgerea in adancime

- se viziteaza nodul curent ( se prelucreaza nodul curent ),dupa care se parcurg in adancime toti vecinii nevizitati ai nodului curent

void adancime(int p)
{ prelucram nodul curent
viz[p]=1;
for(int i=1;i<=n;i++)
if(a[p][i]==1 && viz[i]==0)
adancime(i);}

2) Parcurgerea in latime

- se incarca in coada toti vecinii nevizitati ai elementului curent din coada. Algoritmul se incheie,in momentul in care s-a incercat incarcarea in coada a tuturor varfurilor.
- spre deosebire de subprogramul pentru parcurgerea in adancime, unde aveam ca parametru nodul de pornire, in cazul parcurgerii in latime vom avea ca parametru pozitia curenta din vectorul C ( din coada )

void latime(int poz)
{ prelucram c[poz] // nodul curent
for(int k=1;k<=n;k++)
if(viz[k]==0 && A[c[poz][k]]==1)
{ viz[k]=1;
nrc++;
c[nrc]=k; }
if(poz<n)
latime(poz+1);}

Apel : cout<<"nodul de pornire : "; cin>>p;
c[1]=p;  nrc=1;  viz[p]=1; latime(1);

GRAFURI BIPARTITE

Se numeste graf bipartit , graful G=(X,U) cu proprietatea ca exista o partitie a multimii X in doua submultimi X1,X2, astfel incat orice muchie are o extremitate in multimea X1 si cealalta extremitatea in multimea X2.

Vom marca nodurile grafului cu 1 , respectiv -1 , astfel incat 2 noduri adiacente sa aiba marcaje diferite, in cazul in care vom reusi sa avem un astfel de marcaj, vom spune ca graful nostru este bipartit.

In cazul in care ajungem sa marcam un nod deja marcat cu o alta valoare, vom spune ca graful nu este bipartit.
Valoarea marcajului fiecarui nod va fi retinuta in vectorul marca[i]

void verifica(int p , int vm)
{ marca[p]=vm;
viz[p]=1;
vm=(-1)*vm;
for(int k=1;k<=n;k++)
if(a[p][k]==1)
if(viz[k]==0)
verifica(k,vm);
else
if(marca[k]!=vm)
bipartit=0;}

Apel:
bipartit=1;
vm=1;
verifica(1,1);

CONEXITATE IN GRAFURI. COMPONENTE CONEXE

Se numeste graf conex, un graf cu proprietatea ca oricare 2 noduri sunt legate printr-un lant.
Se numeste componenta conexa a unui graf, un subgraf maximal in raport cu proprietatea de conexitate.
Grafurile conexe au o singura componenta conexa.

Determinarea componentelor conexe:

int nrc=0; // nr de componente conexe
for(int i=1;i<=n;i++)
if(viz[i]==0)
{cout<<"comp conexa";
adancime(i);}
if(nrc==1)
cout<<"graf conex";

GRAFURI HAMILTONIENE

Se numeste lant hamiltonian , un lant elementar care trece prin toate varfurile grafului.
Se numeste ciclu hamiltonian , un lant hamiltonian in care extremitatea initiala coincide cu extremitatea finala.
Se numeste graf hamiltonian , un graf care contine un ciclu hamiltonian.

Daca intr-un graf neorientat G=(X,U) cu card(x)>=3 orice nod Z din X verifica relatia d(z)>=(n/2) atunci G este graf hamiltonian.

GRAFURI EULERIENE

Se numeste lant eulerian , un lant simplu care trece prin toate muchiile grafului.
Se numeste ciclu eulerian , un lant eulerian in care extremitatea initiala coincide cu extremitatea finala.
Se numeste graf eulerian , un graf care contine un ciclu eulerian.

G este eulerian daca si numai daca G este conex si gradele tuturor varfurilor sunt numere pare ( daca graful nu are noduri izolate )


ARBORI ( ARBORI LIBERI )

Se numeste arbore, un graf neorientat conex fara cicluri.
Orice arbore cu n noduri are n-1 muchii.
Prin adaugarea unei singure muchii, obtinem un ciclu iar prin scoaterea unei singure muchii graful nu mai este conex.


GRAFURI ORIENTATE

Se numeste graf orientat, perechea G=(X,U) unde X este multime finita si nevida, numita multimea nodurilor, iar U este formata din perechi ordonate de elemente din X si poarta denumirea de multimea arcelor.

In cazul in care intre doua noduri x1,x2 exista arc de la x1 la x2 si de la x2 la x1, vom spune ca avem arc dublu.

(x1,x2) - Vom spune ca nodurile x1,x2 sunt adiacente iar arcul (x1,x2) este incident in nodul x2.

S(x1) - Multimea succesorilor nodului x1.
U+(x1) - Multimea arcelor care au extemitatea initiala in nodul x1.
P(x1) - Multimea predecesorilor nodului x1.
U-(x1) - Multimea arcelor care au extremitatea finala in nodul x1.

Nr grafurilor orientate care se pot construi cu n noduri este 4^(Combinari de n luate cate 2).

Graf complet : graf in care oricare doua noduri sunt adiacente. Intr-un graf complet exista intre n(n-1)/2 si n(n-1) arce.
Cu un graf orientat cu n noduri putem forma 3^(Combinari de n luate cate 2) grafuri complete.

Definim gradul exterior nodului x1, notat d+(x1) ca fiind nr de succesori ai nodului x1.
Definim gradul interior nodului x1, notat d-(x1) ca fiind nr de predecesori ai nodului x1.

Nod izolat <=> d+(x1)=d-(x1)=0        Nod terminal <=> d+(x1)+d-(x1)=1

Intr-un graf orientat, suma gradelor interioare este egala cu suma gradelor exterioare si este egala cu nr de arce.

Matricea de adiacenta { 1 daca exista arc de la i la j si 0 altfel }

d+(xi) = suma elementelor pe linia xi.
d-(xi) = suma elementelor pe coloana xi.

Nodul sursa al unui graf apare pe primul loc din pereche de n-1 ori si niciodata pe locul al doilea.
Nodul destinatie al unui graf apare pe al doilea loc din pereche de n-1 ori si niciodata pe primul loc.

Matricea de incidenta { 1 daca nodul i este extremitatea initiala pentru arcul j ,-1 daca nodul i este extremitatea finala pentru arcul j, si 0 altfel } ( nr de valori de 1 pe linia i reprezinta gradul exterior al nodului i , iar numarul de valori de -1 gradul interior )

Listele de adiacenta.

1) Lisa succesorilor , notata L+, unde L+[i], multimea tuturor nodurilor j , cu prop ca (i,j) apartine U.
2) Lisa predecesorilor , notata L-, unde L-[i], multimea tuturor nodurilor j , cu prop ca (j,i) apartine U.

Vectorul de arce.
- o structura cu doua campuri in care vom retine extremitatea initiala si extremitatea finala ( struct arc{int ei,ef;}; arc v[20]; )

Lant.Drum.Circuit.

Se numeste lant, succesiunea de noduri x1,x2,..xk cu proprietatea ca oricare ar fi i de la 1 la k-1, nodurile xi si xi+1 sunt adiacente.
Un lant cu arcele distincte poarta denumirea de lant simplu.
Un lant cu nodurile distincte poarta denumirea de lant elementar.

Se numeste drum, un lant in care toate arcele au aceeasi orientare.
Se numeste drum elementar, un drum cu nodurile distincte.
Se numeste drum simplu, un drum cu arcele distincte.

Se numeste circuit, un drum simplu in care extremitatea initiala coincide cu extremitatea finala.
Se numeste circuit elementar, un circuit cu nodurile distincte cu exceptia primului si ultimului nod.

Conexitate in grafuri orientate.

void adancipe(int p)
{ viz[p]=1;
// prelucram nodul p
for(int i=1;i<=n;i++)
if(viz[i]==0&&(a[p][i]==1||a[i][p]==1))
adancime(i);}

for(int i=1;i<=n;i++)
if(viz[i]==0)
{ nrc++;
cout<<"comp conexa ";
adancime(p);}

Graf turneu

Un graf orientat G=(X,U) se numeste graf turneu, daca si numai daca intre oricare doua noduri exista un arc si numai unul.
Orice graf turneu este graf complet. Avem 2^(Combinari de n luate cate 2 ) grafuri turneu. In orice graf turneu exista un drum elementar ce trece prin toate varfurile grafului.

Verificarea daca un graf este turneu :

int verif()
{
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    if((a[i][j]==0&&a[j][i]==0)||(a[j][i]==1&&a[i][j]==1)||a[i][i]==1)
       return 0;
    return 1;}


Matricea Drumurilor. ( Algoritmul lui Roy Warshall )

Definim matricea drumurilor asociata unui graf orientat in modul urmator : D[i][j]=1 daca exista drum de la i la j si 0 altfel.

Algoritmul Roy Warshall foloseste matricea de adiacenta, construirea matricei drumurilor facandu-se in modul urmator:

1) Se copie matricea de adiacenta in matricea drumurilor.
2) Pentru fiecare pereche i,j cu D[i][j]==0 se cauta un nod k astfel incat D[i][k]==1 && D[k][j]==1 cu i!=k si k!=j.

void matricea_drumurilor()
{ for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=a[i][j];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=k&&d[i][k]==1)
for(int j=1;j<=n;j++)
if(j!=k&&d[k][j]==1)
d[i][j]=1;}

Grafuri tare conexe

Vom spune ca graful G=(X,U) este tare conex daca si numai daca oricare ar fi x1,x2 din X, exista drum de la x1 la x2 si de la x2 la x1.
Se numeste componenta tare conexa a unui graf orientat, un subgraf maximal in raport cu proprietatea de tare conexitate.
Pentru a verifica daca un graf este tare conex, vom construi matricea drumurilor si vom verifica daca D[i][j]=1 oricare ar fi i!=j.

int verif() // daca este tare conex
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j&&d[i][j]==0)
        return 0;
    return 1;
}

Determinarea drumurilor de cost minim/maxim ( Algoritmul lui Roy-Floyd )

Algoritmul va modifica matricea costurilor astfel incat in urma rularii algoritmului lui Roy-Floyd c[i][j] va contine costul drumului minim/maxim pentru nodurile i si j.

void rf()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    if(k!=i&&c[i][k]!=32000)
    for(int j=1;j<=n;j++)
    if(k!=j&&c[k][j]!=32000)
    if(c[i][j]>c[k][j]+c[i][k])
    c[i][j]=c[i][k]+c[k][j];
}

Afisarea drumului de cost minim de la x la y ( recursiv )

void afisdrum(int x,int y)
{
    int OK=0;
    for(int k=1;k<=n&&!OK;k++)
        if(a[x][y]==a[x][k]+a[k][y]&&k!=x&&k!=y)
        {
            OK=1;
            afisdrum(x,k);
            afisdrum(k,y);
        }
    if(OK==0)
        cout<<y<<" ";} // iar inainte de apel cout<<x<<" ";