Structuri de Date 2023

Structuri de Date

Curs 10: Grafuri

Cuprins:

Ce este un graf?
Clasificarea grafurilor
O groază de terminologie legată de grafuri
Reprezentare prin matrice de adiacență
Reprezentare prin listă de adiacență
Parcurgere în adâncime
Parcurgere în lățime
Găsirea componentelor conexe (graf neorientat)
Găsirea componentelor tare conexe (graf orientat)

1. Ce este un graf?

Definiţie: Se numeşte graf neorientat un tuplu (V,E) unde:

V este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri (vertices),
iar E este o mulţime de perechi de vârfuri numite muchii (edges).

Pentru graful de mai sus avem:

V={1,2,3,4,5,6,7}

card V = |V| = 7

E ={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4), (4,5), (6,7)}

card E = |E| = 8

Principala utilizare a grafurilor este modelarea de retele (networks):

de transport
1. rutier
2. feroviar
3. aerian
de internet (muchie = conexiune fizica)
de socializare (muchie = relatie de prietenie)
de referinta
1. hiperlinkuri intre site-uri
2. citari intre autori
foarte multe altele (aproape orice sistem care devine suficient de mare se modeleaza prin evidentierea componentelor care devin varfuri si legaturilor intre componente care devin muchii)

2. Clasificarea grafurilor

Graf neorientat.

Graf orientat.

Relația dintre vârfuri poate să fie:

neorientată (a,b) = (b,a) -> grafuri neorientate -> relația se numește muchie
orientată (a,b) ≠ (b,a) -> grafuri orientate -> relația se numește arc

Ambele modele apar în modelarea rețelelor. Spre exemplu pentru o rețea de socializare:

relația de prietenie este neorientată: fiecare utilizator este prieten cu celălalt
relația de follower este orientată: doar unul dintre utilizatori îl urmărește pe celălalt

Dacă este prezentă informație adițională în muchii:

grafuri ponderate (weighted)
grafuri neponderate

Grafurile ponderate se folosesc în multe situații. Ponderea poate să fie:

ping (în rețele de calculatoare)
distanța rutieră
etc.

3. O groază de terminologie legată de grafuri

Definiţie: Numim muchii adiacente două muchii cu o extremitate comună. Pentru exemplul de alături, muchiile [1,3] şi [3,2] sunt muchii adiacente pentru că au ca extremitate comună nodul 3.

Definiţie: Un graf parţial al grafului G=(V,E) este un graf G1=(V,E1) astfel încât:

G1 are aceeaşi mulţime de vârfuri ca G
E1 este inclus sau egal cu E,

Un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii.

Definiţie: Un subgraf al unui graf G=(V,E) este un graf H(V1,E1) astfel încât:

V1 este inclus in V
E1 conţine toate muchiile din E care au ambele extremităţi în V1

Un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri.

Definiţie: Gradul unui vârf x este numărul muchiile incidente cu x. Gradul (degree) vârfului x se notează d(x).

Definiţie: Un vârf care are gradul 0 se numeşte vârf izolat.

Definiţie: Un vârf care are gradul 1 se numeşte vârf terminal.

Propoziţie: Dacă un graf neorientat G(V,U) are m muchii şi n vârfuri, iar V={x1,x2,...,xn} atunci d(x1)+d(x2)+...+d(xn)=2*m.

Corolar: În orice graf neorientat G există un număr par de vârfuri cu grad impar.

În grafuri orientate se folosesc notațiile:

grad intern = numărul de muchii care sosesc în vârf
grad extern = numărul de muchii care pleacă din vârf

Definiţie: Se numeşte graf complet (neorientat) cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.

Propoziţie: Un graf complet Kn are n(n-1)/2 muchii.

Definiţie: Un graf G=(V,E) se numeşte bipartit dacă există două mulţimi nevide A, B astfel încât:

V=A U B

A ∩ B = ∅

şi orice muchie a lui G are o extremitate în A iar cealaltă în B.

Definiţie: Un graf bipartit se numeşte complet dacă pentru orice x din A şi y din B, există muchia (x,y).

Definiţie: Se numeşte lanţ în G secvenţa de vârfuri L=[xi1,xi2,...,xik] cu proprietate că orice două noduri consecutive din lanţ sunt adiacente, adică

[xi1,xi2], [xi2,xi3], ...,

[xik-1,xik]

Definiţie: Dacă vârfurile xi1, xi2, ..., xik sunt diferite două câte două atunci lanţul se numeşte lanţ elementar.

În caz contrar, lanţul este lanţ ne-elementar.

Cu alte cuvinte, un lanţ elementar este un lanţ care nu trece de două ori prin acelaşi vârf.

Definiţie: Se numeşte ciclu în G un lanţ L pentru care xi1=xik şi toate muchiile adiacente

[xi1, xi2], [xi2, xi3], ...,

[xik-1, xik]

sunt diferite.

Definiţie: Se numeşte ciclu elementar un ciclu care are proprietatea că oricare două vârfuri ale sale, cu excepţia primului şi ultimului, sunt diferite două câte două. În caz contrar, ciclul este un ciclu neelementar.

Definiţie: Se numeşte componentă conexă a grafului neorientat G=(V,E) un subgraf G1=(V1,E1) al lui G care are proprietatea că nu există nici un lanţ care să lege un vârf din V1 cu un vârf din V-V1.

Definiţie: Un graf G se numeşte conex dacă pentru orice două vârfuri x şi y diferite ale sale există un lanţ ce le leagă.

Definiţie: Se numeşte componentă tare conexă (strongly connected) a grafului orientat G=(V,E) un subgraf maximal G1=(V1,E1), al lui G care are proprietatea că nu există nici un lanţ orientat care să lege un vârf din V1 cu un vârf din V-V1.

Definiţie: Un graf G se numeşte tare conex(strongly connected) dacă pentru orice două vârfuri x şi y diferite ale sale există un lanţ orientat ce le leagă.

Mai sus grafurile au fost descrise algebric.

Avem nevoie de reprezentări computaționale pentru grafuri.

4. Reprezentare prin matrice de adiacență

struct graf{ int adiacenta[200][200]; int nod_maxim=0;//cand parcurgem sa stim pana la ce nod ne uitam graf(){ for (int i=0;i<200;i++) for (int j=0;j<200;j++) adiacenta[i][j]=0; } void adauga_muchie(int nod_sursa, int nod_destinatie){ adiacenta[nod_sursa][nod_destinatie]=1; if (nod_maxim<nod_sursa) nod_maxim=nod_sursa;
//PENTRU GRAF NEORIENTAT: adiacenta[nod_destinatie][nod_sursa]=1; if (nod_maxim<nod_destinatie) nod_maxim=nod_destinatie; } void afisare(){ for (int i=1;i<=nod_maxim;i++){ for (int j=1;j<=nod_maxim;j++) cout<<adiacenta[i][j]<<" "; cout<<endl;} }};

5. Reprezentare prin listă de adiacență

struct graf{    lista adiacenta[200];//cate o lista cu vecinii fiecarui nod din graf    int nod_maxim=0;//cand parcurgem sa stim pana la ce nod ne uitam
    void adauga_muchie(int nod_sursa, int nod_destinatie){        adiacenta[nod_sursa].insert_la_final(nod_destinatie);        if (nod_maxim<nod_sursa)            nod_maxim=nod_sursa;        //PENTRU GRAF NEORIENTAT:        adiacenta[nod_destinatie].insert_la_final(nod_sursa);        if (nod_maxim<nod_destinatie)            nod_maxim=nod_destinatie;    }
    void afisare(){        for (int i=0; i<=nod_maxim;i++){            if (adiacenta[i].primul_element!=NULL){                cout<<i<<" : ";                adiacenta[i].afisare();            }        }    }
};

6. Parcurgere în adâncime

DFS

Depth first search (DFS)

Se parcurge si marcheaza ca vizitat primul vecin nevizitat.

void parcurgere_in_adancime(int nod_start){ //parcurgerea primului vecin nevizitat primul cout<<"DFS parcurgere_in_adancime: "; int* vizitat = new int[nod_maxim+1]; for (int i=0;i<=nod_maxim;i++) vizitat[i]=0; recursie_parcurgere_in_adancime(vizitat, nod_start); cout<<endl;}
void recursie_parcurgere_in_adancime(int* vizitat, int nod_curent){ //functie recursiva ajutatoare pentru parcurgerea in adancime, alternativ se poate folosi o stiva cout<<nod_curent<<" "; vizitat[nod_curent]=1; for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next) if (vizitat[pointer->info]==0) recursie_parcurgere_in_adancime(vizitat,pointer->info);}

7. Parcurgere în lățime

Breadth first search (BFS)

0. Nodul de start se marcheaza ca vizitat.

Se pun toti vecinii nodului curent intr-o coada si se marcheaza ca vizitati.
Se reia pasul 1 cu primul nod din coada.

void parcurgere_in_latime(int nod_start){    //parcurgerea tuturor vecinilor in ordine, apoi vecinii primului vecin etc...    cout<<"BFS parcurgere_in_latime: ";    int* vizitat = new int[nod_maxim+1];    for (int i=0;i<=nod_maxim;i++)        vizitat[i]=0;    coada_cu_lista coada;    coada.enqueue(nod_start);    vizitat[nod_start]=1;
    while (coada.L.primul_element!=NULL){        int nod_curent = coada.dequeue();        cout<<nod_curent<<" ";
        for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next)            if (vizitat[pointer->info]==0){                vizitat[pointer->info]=1;                coada.enqueue(pointer->info);            }    }    cout<<endl;}

8. Găsirea componentelor conexe (graf neorientat)

Lansăm parcurgerea noastră preferată din primul nod nevizitat.
Marcăm toate nodurile parcurse cu un întreg unic. (Colorăm nodurile)
Continuăm cu următorul nod nevizitat, folosind alt întreg (culoare).

void conexe(){ int* vizitat = new int[nod_maxim+1]; int culoare=1; for (int i=1;i<=nod_maxim;i++) vizitat[i]=0; for (int i=1;i<=nod_maxim;i++) if (vizitat[i]==0){ recursie_conexe(vizitat, i, culoare); culoare++; cout<<endl; } cout<<endl;}
void recursie_conexe(int* vizitat, int nod_curent, int culoare){ cout<<nod_curent<<" "; vizitat[nod_curent]=culoare; for (nod_lista* pointer = adiacenta[nod_curent].primul_element; pointer !=NULL;pointer = pointer->next) if (vizitat[pointer->info]==0) recursie_conexe(vizitat,pointer->info,culoare);}

Google Sites

Report abuse