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:
 
Grafuri. Traversari pe grafuri
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 

(ˆVˆ <=> |V| -cardinal de V)

Definitie: t4c11ch
Fie G = (V, E) o multime, Œn care V este o multime de noduri finita, ˆVˆ = n , si E o multime de arce,
E = A(i, j), i, j N S. G se numeste graf, E<=VxV.
Avem: grafuri orientate Œn care (i, j)1=(j, i) grafuri neorientate Œn care (i, j)apartine lui E->(j, i)apartine lui E

Observatie: Un arbore este un caz particular de graf.

Definitii: i se numeste predecesor al lui j; j se numeste succesor al lui i;
(i, j) este adiacent cu i si j; i, j adiacente;
Ei = A k, (k, i) ES multimea de vecini la intrare;
E'i = A j, (i, j) ES multimea de vecini la iesire;
Ei reunit E'i multimea vecinilor. grad_intrare(i) = in_degree(i) = ˆEiˆ grad_ie_ire(i) = out_degree(i) = ˆ E'iˆ
Pentru un graf neorientat (G - neorientat), Ei E'i si degree(i)= ˆEiˆ.

Definitie
Se numeste drum orientat Œntr-un graf de la x la y secventa de noduri
D = (i1 = x, i2, ... , in = y),
(ik, ik+1) E, k=1,n . (ik <=> i indoce k)
Drumul D este neorientat, daca (ik, ik+1) apartine E sau (ik+1, ik)apartine E

Definitie
Se numeste graf conex graful pentru care doua noduri (x, y) V, D un drum de la x la y.
Un graf este complet daca fiecare nod este conectat cu oricare din celelalte noduri: E = VxV \ A(i, i), iaprtine VS

Definitie
Fie G = (V, E) un graf. Se numeste subgraf al grafului G, un graf
G' = (V', E'), astfel Œncƒt V' inclus in V,
E'<=(V'xV') intersectat cu E

Reprezentari
1) Matrice de adiacenta
Fie G = (V, E) ,ˆVˆ = n. Se determina matricea de adiacenta astfel:

Un graf este etichetat daca o functie definita pe E R, adica fiecarui arc i se asociaza o valoare. Astfel de grafuri se reprezinta prin matrici de colectivitate:

Complexitate:
O(1), (i, j) apartine E
O(n), Ei, E'i, indegree(i), outdegree(i)
O(n2), spatiu

1) Liste de adiacenta directa

Definitie
Fie G = (V, E) un graf, ˆVˆ = n , V = A1, 2, ... , nS. Se numeste lista de adiacenta asociata acestui graf o colectie de n pointeri (1, 2, ... , n), fiecare pointer continƒnd adresa unei liste dupa regula urmatoare: L(i) da adresa listei Œnlantuite care contine toti succesorii lui i.




L(i)->Ei

Exemplu:

3) Liste de adiacente inverse
(i,j) apartine E
O(ˆEˆ)- cardinal de E
L'(1, 2, ..., n), L'(i)->E'i
Ei: O(ˆEˆ) sau O(maxout_degree)
E'i: O(ˆEˆ) spatiu: O(ˆEˆ + n)

4) Liste de adiacenta dubla
(i,j) , E, (i,j, e(i,j))

Operatii pe grafuri, traversari
La grafuri se folosesc operatii Œntre elemente ((i,j) adiacente, etc), operatii de traversare pe grafuri. Se numeste traversare pe graf o procedura de traversare, pentru un scop bine definit, prin toate nodurile.
Exista: traversari Œn adƒncime A depth first traversari Œn latime A bmedth first

Proceduri:

dfs(G, i) // mark(1... n) initializat cu
// (00 ... 0) A ext
A // procesare() procesare(i) mark(i) = 1 for fiecare k V cu (i,k) E
| if mark(k) = 0
|_dfs(k)
S

bfs(G, i)
A // mark(1... n) initializat cu (0 ... 0) ext
// o coada q isempty, a= pop(p), put(q) ext procesare(i) mark(i) = 1 put(q, i)
while(isEmpty(q) = N0)) do
| k = pop(q)
| for fiecare j V , (k,j) E
| | if(mark(j)=0)
| | | procesare(j)
| | | mark(j) = 1
| | |_ put(q,j)
S

1) Matrice adiacenta

dfs(M, i)
A procesare(i) mark(i) = 1 for k = 1 to n
| if (M(i,k) = 1)
| | if mark(k) = 0
|_ |_ dfs(k)
S

2) Liste de adiacenta directa

dfs(L, i)
A procesare(i) mark(i) = 1 p = P(i)
while p 0
| if mark(data(p)) 0
| dfs(data(p))
|_ p = link(p)
S

Arbori de acoperire pe grafuri

Fie G(V, E) un graf.
Se numeste arbore de acoperire un arbore T = (V, E') , cu E'<=E

Observatie: Algoritmii dfs, bfs produc arbori de acoperire.


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