Teoria grafurilor

Reprezentarile prin grafuri sunt utilizate in special pentru vizualizarea sistemelor

si situatiilor complexe. Intre doua puncte pot exista unul sau mai multe segmente (in

functie de cate relatii dintre acestea, care ne intereseaza, exista) iar segmentelor li se pot

asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele),

numere care sa exprime intensitatea relatiilor dintre componente etc.

Definitia 1 Numim graf o pereche ordonata de multimi, notata G=(X,A), unde X

este o multime finita si nevida de elemente numite noduri sau varfuri, iar A este o

multime de perechi (ordonate sau neordonate) de elemente din X numite muchii (daca

sunt perechi neordonate) sau arce (daca sunt perechi ordonate). In primul caz, graful se

numeste orientat, altfel acesta este neorientat.

Definitia 2 Se numeste multigraf un triplet G = (X, A, f) in care X si A sunt doua

multimi iar f este o functie, definita pe produsul vectorial al lui X cu el insusi (X2 =

X?X), care ia valori in multimea partilor multimii A (notata P(A))

Multimea X se numeste multimea nodurilor multigrafului si elementele sale se

numesc noduri (sau varfuri) ale multigrafului, iar A reprezinta multimea relatiilor

(legaturilor) posibile intre doua noduri ale multigrafului.

Definitia 3 Se numeste graf orientat un multigraf in care multimea A are un

singur element: A = {a}.

In acest caz multimea partilor multimii A are doar doua elemente: multimea vida

- si intreaga multime A. Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin

functia f multimea A atunci spunem ca exista arc de la nodul xi la nodul xj iar perechea

(xi,xj) se va numi arcul (xi,xj). Nodul xi se numeste nod initial sau extremitate initiala a

arcului (xi,xj) iar nodul xj se numeste nod final sau extremitate finala a arcului (xi,xj).

Arcul (xi,xj) este incident spre interior varfului xj si incident spre exterior varfului xi.

Daca pentru un arc nodul initial coincide cu nodul final atunci acesta se numeste bucla.

Nodurile xi si xj se vor numi adiacente daca exista cel putin unul din arcele (xi,xj) si

(xj,xi).

Este evident ca a cunoaste un graf orientat este echivalent cu a cunoaste varfurile

si arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X

este multimea varfurilor sale, iar U multimea arcelor sale.

De asemenea, putem cunoaste un graf orientat cunoscand multimea nodurilor si,

pentru fiecare nod, multimea arcelor incidente spre exterior.

Definitia 4 Se numeste graf neorientat un multigraf in care multimea A are un

singur element iar functia f are proprietatea:

f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi si xj din X

In aceste conditii, daca f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientata

{xi,xj} este o muchie iar daca f[(xi,xj)] = f[(xj,xi)] = - spunem ca nu exista muchie intre

varfurile xi si xj.

In continuare vom folosi denumirea de graf in locul celei de graf orientat iar in

cazul in care graful este neorientat vom specifica acest fapt la momentul respectiv.

2. Moduri de reprezentare ale unui graf

A. O prima modalitate de reprezentare este listarea efectiva a tuturor nodurilor si

a arcelor sale.

B. Putem reprezenta graful dand pentru fiecare nod multimea nodurilor cu care

formeaza arce in care el este pe prima pozitie.

C. Putem reprezenta geometric graful, printr-un desen in plan, reprezentand

fiecare nod printr-un punct si fiecare arc printr-un segment de curba care are

ca extremitati nodurile arcului si pe care este trecuta o sageata orientata de la

nodul initial spre cel final.

D. Putem folosi o reprezentare geometrica in care nodurile sunt reprezentate de

doua ori, in doua siruri paralele, de la fiecare nod din unul din siruri plecand

sageti spre nodurile cu care formeaza arce in care el este pe prima pozitie, de

pe al doilea sir (reprezentarea prin corespondenta).

E. Un graf poate fi reprezentat printr-o matrice patratica booleana, de dimensiune

egala cu numarul de noduri, in care pe o pozitie aij va fi 1 daca exista arcul

(xi,xj) si 0 in caz contrar, numita matricea adiacentelor directe.

F. Un graf poate fi reprezentat printr-o matrice patratica latina, de dimensiune

egala cu numarul de noduri, in care pe o pozitie aij va fi xixj daca exista arcul

(xi,xj) si 0 in caz contrar.

Exemplu: Daca in reprezentarea A avem graful G = (X,U), unde X = {x1, x2, x3,

x4, x5, x6} si U = {(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1), (x3,x2),

(x4,x5), (x5,x2), (x6,x4)}, atunci in celelalte reprezentari vom avea:

B x1 ? {x1, x2, x4, x5} C

x2 ? {x3, x4, x6}

x3 ? {x1, x2}

x4 ? {x5}

x5 ? {x2}

x6 ? {x4}

D (reprezentarea prin corespondenta)

x1 x2 x3 x4 x5 x6

x1 x2 x3 x4 x5 x6

x1 x2

x6

x5 x4

x3

E F

3. Concepte de baza in teoria grafurilor

1. semigraf interior al unui nod xk: este multimea arcelor ?

Uxk = {(xj,xk)/ (xj,xk)

? U} care sunt incidente spre interior nodului xk;

2. semigraf exterior al unui nod xk: este multimea arcelor ?

Uxk = {(xk,xi)/ (xk,xi)

? U} care sunt incidente spre exterior nodului xk;

3. semigradul interior al unui nod xk: este numarul arcelor care sunt incidente

spre interior nodului xk = cardinalul lui ?

Uxk si se noteaza cu ?

xk ? ;

4. semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente

spre exterior nodului xk = cardinalul lui ?

Uxk si se noteaza cu ?

xk ? ;

5. gradul unui nod xk: este suma semigradelor nodului xk:

xk ? = ?

xk ? + ?

xk ? ;

6. nod izolat: este un nod cu gradul 0;

7. nod suspendat: este un nod cu gradul 1;

8. arce adiacente: arce care au o extremitate comuna;

9. drum intr-un graf: o multime ordonata de noduri ale grafului: (x1, x2, ..., xk),

cu proprietatea ca exista in graf toate arcele de forma (xi,xi+1) i = 1,...,k-1;

10. lungimea unui drum: este numarul arcelor care il formeaza;

11. drum elementar: un drum in care fiecare nod apare o singura data;

12. drum simplu: un drum in care fiecare arc apare o singura data;

13. putere de atingere a unui nod xi ? X in graful G: numarul de noduri la care

se poate ajunge din xi. Puterea de atingere se noteaza cu p(xi), 1 ? i ? n si

evident p(xi) ? ?

xi ? .

14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;

15. drum eulerian: un drum simplu care contine toate arcele grafului;

16. lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;

17. circuit: un drum in care nodul initial coincide cu cel final;

18. circuit elementar: un drum in care fiecare nod apare o singura data, cu

exceptia celui final, care coincide cu cel initial;

19. circuit simplu: un drum in care fiecare arc apare o singura data;

20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

www.referat.ro

2. www.inf.ucv.ro

3. www.cs.utt.ro

4. www.referate.acasa.ro

5. Curs de Combinatorica si teoria grafurilor.