Document, comentariu, eseu, bacalaureat, liceu si facultate
Top documenteAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate



Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 

Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
ELEMENTE DE TEORIA GRAFURILOR
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 

1. Notiuni generale

In general, pentru situatiile care necesita la rezolvare un oarecare efort mintal (si un caz tipic este cel al celor din economie), se cauta, in primul rand, o metoda de reprezentare a lor care sa permita receptarea intregii probleme dintr-o privire (pe cat posibil) si prin care sa se evidentieze cat mai clar toate aspectele acesteia.

In acest scop se folosesc imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe. In general, vom reprezenta componentele acestora prin puncte in plan iar relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile in punctele corespunzatoare. 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.

Este evident, totusi, ca aceasta metoda are limite, atat din punct de vedere uman (prea multe puncte si segmente vor face desenul atat de complicat incat se va pierde chiar scopul pentru care a fost creat – claritatea si simplitatea reprezentarii, aceasta devenind neinteligibila) cat si din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).




Din acest motiv, alaturi de expunerea naiv-intuitiva a ceea ce este un graf, data mai sus, se impune atat o definitie riguroasa cat si alte modalitati de reprezentare a acestora, adecvate in general rezolvarilor matematice.

Definitia 1 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 2 Se numeste graf orientat un multigraf in care multimea A are un singur element: A = AaS.

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 x j se vor numi adiacente daca exista cel putin unul

din arcele (xi,xj) si (xj,xi).

Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea vida atunci spunem ca nu exista arc de la nodul xi la nodul xj.

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. Din acest motiv putem defini un graf orientat ca o pereche (X,G) unde X este perechea nodurilor iar G este o functie definita pe X cu valori in

multimea partilor lui X, valoarea acesteia intr-un nod xi, G(xi) X fiind multimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea initiala.

Definitia 3 Se numeste graf neorientat un multigraf in care multimea A are un singur element iar functia f are proprietatea:

fa(xi,xj)i = fa(xj,xi)i , oricare ar fi nodurile xi si xdin X

In aceste conditii, daca fa(xi,xj)i = fa(xj,xi)i = A atunci perechea neorientata Axi,xjS este o j

muchie iar daca fa(xi,xj)i = fa(xj,xi)i = spunem ca nu exista muchie intre varfurile xi si xj. Deoarece, in cele mai multe din cazurile practice care vor fi analizate in acest capitol,

situatia este modelata matematic printr-un graf orientat, vom folosi, pentru simplificarea expunerii, 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(cerculet) 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 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 = Ax1, x2, x3, x4, x5, x6S

si U = A(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1), (x3,x2), (x4,x5), (x5,x2), (x6,x4)S, atunci in celelalte reprezentari vom avea:

B x1 Ax1, x2, x4, x5S C

x2 Ax3, x4, x6S x3 Ax1, x2S x1 x2

x4 Ax5S x5 Ax2S x6 x3

x6 Ax4S

D (reprezentarea prin corespondenta) x5 x4

x1 x2 x3 x4 x5 x6

 

 

 

 

x1 x2 x3 x4 x5 x6

E F

x1 x2 x3 x4 x5 x6 x1 1 1 0 1 1 0 x2 0 0 1 1 0 1 x1 x2 x3 x4 x5 x6 x1 x1x1x1x2 0 x1x4x1x5 0 x2 0 0 x2x3x2x4 0 x2x6

x3 1 1 0 0 0 0 x4 0 0 0 0 1 0 x3 x3x1x3x2 0 0 0 0 x4 0 0 0 0 x4x5 0

x5 0 1 0 0 0 0 x6 0 0 0 1 0 0 x5 0 x5x2 0 0 0 0 x6 0 0 0 x6x4 0 0

3. Concepte de baza in teoria grafurilor

1. semigraf interior al unui nod xk: este multimea arcelor U - = A(x j,xk)/ (xj,xk) US care

x k

sunt incidente spre interior nodului xk;

2. semigraf exterior al unui nod xk: este multimea arcelor U + x = A(x k,xi)/ (xk,xi) US care

k

sunt incidente spre exterior nodului xk;

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

- -d

4. semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente spre nodului xk = cardinalul lui U si se noteaza cu ;

x k x k

exterior nodului xk = cardinalul lui U + d + si se noteaza cu ;

x k x k

5. gradul unui nod xk: este suma semigradelor nodului xk: d = d + + d - ;

x k x

Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui document, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)


Noteaza documentul:
In prezent fisierul este notat cu: ? (media unui numar de ? de note primite).

2345678910

 
Copyright© 2005 - 2024 | Trimite document | Harta site | Adauga in favorite
Colt dreapta