ELEMENTE DE TEORIA GRAFURILOR

ELEMENTE DE TEORIA GRAFURILOR

A. Grafuri neorientate

Definitie: Se numeste graf neorientat o pereche de multimi G = (A,B) in care A este multimea nodurilor (este finita si nevida) si B e multimea relatiilor/muchiilor.

B =

B. Grafuri orientate (digrafuri)

Se numeste graf orientat o multime ordonata (A,B) in care A este multimea nodurilor (finita si nevida), iar B este multimea arcelor.

Terminologie

Daca (x,y) apartine de B atunci:

     - x si y sunt noduri adiacente

     - x si y sunt extremitatile arcului (x,y)

     - x si y sunt incidente cu (x,y)

     - in cazul grafurilor orientate:

        - x este extremitatea initiala a (x,y)

        - y este extremitatea finala a (x,y)

     u = (x,y); v = (y,z); => u si v sunt incidente

Exemplu:

1 este adiacent cu 2 si 3

1 si 2 sunt extremitatile (1,2)

nodul 1 este incident cu (1,2)

(5,2) si (2,3) sunt incidente

Gradul unui nod: numarul de muchii incidente cu el

d(x) - gradul nodului x

G₁: d(1) = 2

G₂: d(1) = 3

Pentru grafurile orientate, se definesc:

Gradul exterior al lui x: d⁺(x) = numarul arcelor care pleaca din x

Gradul interior al lui x: d^-(x) = numarul arcelor care intra in x

Exemplu:

pentru G₂: d(1)=3; d⁺(1)=1; d^-(1)=2;

Nodurile de grad 0 se numesc noduri izolate.

Nodurile de grad 1 se numesc noduri terminale.

Proprietati

d⁺(x) + d^-(x) = d(x)

Daca un graf are m muchii sau arce atunci: d(x₁) + d(x₂) + + d(x_n) = 2m

Daca un graf orientat are m arce:

d⁺(x₁) + d⁺(x₂) + + d⁺(x_n) = m

d^-(x₁) + d^-(x₂) + + d^-(x_n) = m

Lanturi. Drumuri

A. Pentru grafuri neorientate

Se numeste lant o succesiune de noduri x₁ x_k, cu proprietatea ca oricare doua noduri vecine (x_i,x_i+1) apartin de B.

x₁, x_k sunt extremitatile lantului.

Lungimea lantului este egala cu numarul de muchii care il compun, k-1.

Daca nodurile din lant sunt distincte, atunci lantul este elementar.

Fig. 1.1

B. Pentru grafuri orientate

Se numeste lant o succesiune de arce u₁, u₂ u_k, cu proprietatea ca oricare doua arce de pe pozitii consecutive au un nod comun. Observatie: nu conteaza ordinea de parcurgere. Se numeste drum o succesiune de noduri x₁, x₂ x_k cu proprietatea ca (x_i,x_i+1) este arc.

Observatie: conteaza ordinea de parcurgere. Daca nodurile sunt distincte, drumul se numeste elementar

Cicluri. Circuite

A.     Pentru grafuri neorientate

Se numeste ciclu intr-un graf neorientat un lant x₁,x₂ x_k si oricare 2 muchii (x_i,x_i+1) sunt distincte.

Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.

Fig. 1.2

Pentru grafuri orientate

Se numeste circuit intr-un graf un drum x₁,x₂ x_k cu proprietatea ca x₁ = x_k si arcele (x_i,x_i+1) sa fie distincte 2 cate 2.

Un circuit in care toate nodurile sunt distincte cu exceptia capetelor se numeste circuit elementar.

Reprezentarea grafurilor in memorie

Reprezentarea prin matrice de adiacenta

Liste de adiacenta

Vector de muchii

Matrice arce-noduri

1. Matricea de adiacenta

A. Pentru grafuri neorientate

a[i,j] = 1, daca intre i si j este muchie

a[i,j] = 0 altfel.

Observatie: Pe diagonala principala toate elementele sunt 0 (nu avem bucle).

Matricea este simetrica fata de diagonala principala, deci: a[i,j] = a[j,i].

Pentru grafuri orientate

a[i,j] = 1, daca exista arcul (i,j);

a[i,j] = 0, altfel.

2. Liste de adiacenta

Pentru fiecare nod se memoreaza o lista a vecinilor sai.

Pentru intregul graf este necesar un vector de liste (P) in care P_i este adresa primului element al listei asociate lui i.

Observatie: pentru grafurile orientate se memoreaza in lista lui i nodurile k pentru care exista arcul (i,k).

Struct elem ;

elem *p[100];

int n;

Fig.1.3

Vector de muchii

struct muchie v[100];

int n,m;

Matricea noduri-arce

Este folosita in special pentru grafurile orientate.

Observatie: matricea noduri-arce poate fi adaptata si pentru grafurile neorientate.

Sunt mai multe tipuri de grafuri:

Graf partial

Fie G=(A,B) si G₁=(A₁,B₁).

Spunem ca G₁ este un graf partial al lui G daca A=A₁ si B₁ este inclus sau egal cu B.

Un graf partial se obtine dintr-un graf, indepartand o parte dintre muchiile sale si pastrand toate nodurile acestuia

2. Subgraful unui graf

Fie G=(A,B) si G₁=(A₁,B₁);

A₁ inclus sau egal cu A; B₁ inclus sau egal cu B.

B₁ =

Subgraful se obtine din graful initial selectand o parte din nodurile sale si o parte din nodurile adiacente cu acesta.

3. Graf complet

Un graf este complet daca oricare doua varfuri distincte sunt adiacente.

4.Grafuri bipartite

Un graf bipartit este bipartit complet daca fiecare nod din multimea A₁ este adiacent cu toate nodurile din A₂ si reciproc.

5. Grafuri conexe

Un graf este conex daca este format dintr-un singur nod sau daca intre oricare doua noduri ale sale exista cel putin un lant.

Se numeste componenta conexa a unui graf un subgraf al sau care este conex si care este maximal in raport cu aceasta proprietate (daca i se adauga un nod isi pierde aceasta proprietate).

Observatie: pentru grafurile orientate nu se tine cont de orientarea arcelor.

Exemplu

Graful    din fig. 2 este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lant. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lantul , dar si pe traseul de noduri (4,1,2) stabilind lantul

Acest graf nu este conex.

6. Grafuri tare conexe

Graful tare conex este un graf orientat G=(X, U), daca pentru oricare doua noduri x si y care apartin lui X, exista un drum de la x la y precum si un drum de la y la x.

Exemplu

Graful cu n=3 din fig. 4 este tare conex.

Pentru a demonstra acest lucru, formam toate perechile posibile de noduri distincte (x, y) cu x, y apartin multimii , si pentru fiecare astfel de pereche cautam un drum de la x la y si un drum de la y la x.

X=1, y=2

De la 1 la 2 - drumul [1,3,2], pe arcele (1,3) si (3,2);

De la 2 la 1 - drumul [2,3,1], pe arcele (2,3) si (3,1).

X=1, y=3

De la 1 la 3 - drumul [1,2,3], pe arcele (1,2) si (2,3);

De la 3 la 1 - drumul [3,2,1], pe arcele (3,2) si (2,1).

X=2, y=3

De la 2 la 3 - drumul [2,1,3], pe arcele (2,1) si (1,3);

De la 3 la 2 - drumul [3,1,2], pe arcele (3,1) si (1,2).

Componenta tare conexa

Un subgraf se obtine dintr-un graf G= (X, U) eliminand niste varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase.

Fie un subgraf tare conex G₁=(X₁, U₁) al grafului G=(X, U). Adaugam la subgraf un nod x care nu face parte din multimea nodurilor sale (x apartine X-X₁). Obtinem astfel multimea de varfuri X₁ reunit cu . Subgraful indus pe multimea X₁ reunit cu se obtine luand si arcele care trec prin nodul x.

Daca acest subgraf nu mai este tare conex, atunci el se numeste componenta tare conexa.

Exemplu:

Acesta este graful G=(X,U) tare conex.

Din el eliminam nodul 4.

Am obtinut astfel subgraful tare conex G₁=(X₁, U₁).

Acestui graf ii adaugam un nod x care nu face parte din multimea nodurilor subgrafului G₁.

Graful obtinut    este componenta tare conexa.

7. Grafuri hamiltoniene

Lant hamiltonian: lant elementar care contine toate nodurile grafului.

Ciclu hamiltonian: ciclu elementar care contine toate nodurile grafului.

Graf hamiltonian: graf care contine un ciclu hamiltonian.

8. Grafuri euleriene

Ciclu eulerian: ciclu care trece prin toate muchiile unui graf exact o data.

Graf eulerian: graf care contine cel putin un ciclu eulerian.

O parcurgere a unui graf isi propune sa ia in discutie fiecare nod al grafului exact o singura data, pornind de la un nod ales, numit in continuare nod sursa.

Parcurgerea in latime viziteaza intai toti vecinii unui nod dat si numai dupa ce epuizeaza toti vecinii trece la un alt nod. Parcurgerea in latime (BFS) foloseste o coada pentru a putea vizita toti vecinii unui nod dat inainte de a-l marca drept prelucrat. Se poate folosi inclusiv pentru determinarea drumurilor de lungime minima si returneaza cate un arbore pentru fiecare componenta conexa.

Fig. 1.4

Parcurgerea in adancime isi propune sa mearga din vecin in vecin cat de mult se poate, "adancindu-se" astfel in structura grafului.

Parcurgerea in adancime (DFS) se poate implementa in forma recursiva, iar principiul sau de functionare sta la baza BKT. DFS. Se foloseste in sortarea topologica si furnizeaza unul sau mai multi arbori de adancime.