Structuri arborescente(grafuri de tip arbore)

Structuri arborescenteDefiniie. Graful G este arbore dac G este aciclic i conex.

Structuri arborescenteDefiniie. Fie G=(V,E) graf arbore. Subgraful H=(V1,E1) al lui G este subarbore al lui G dac H este graf arbore.

Structuri arborescenteFie G=(V,E) un graf. Urmtoarele afirmaii snt echivalente:G este graf arbore (aciclic i conex);G este graf conex minimal: oricare ar fi eE, prin eliminarea muchiei e din E, graful rezultat nu este conex;G este graf aciclic maximal: prin adugarea unei noi muchii n graf rezult cel puin un ciclu.

Cum verificm dac un graf este arbore?Verificare conexitate + verificare aciclicitate (alg. Marimont)Verificare aciclicitate i n = m + 1Verificare conexitate i n = m + 1

Structuri arborescenteDefiniie. Se numete graf asimetric un digraf D=(V,E) cu proprietatea c pentru orice uvE, vu nu apartine E. Digraful D este simetric dac pentru orice uvE i vuE.

Structuri arborescenteDefiniie. Fie D=( V, E ) digraf netrivial. Graful G=( V, E ), unde E = { uv / uvE sau vuE} se numete graf suport al digrafului D.

1

2

3

4

5

6

7

Structuri arborescenteDefiniie. Un arbore direcionat este un graf orientat asimetric pentru care graful suport corespunztor este graf arbore.

Definiie. Arborele direcionat T = ( V, E ) este arbore cu rdcin dac exist r V astfel nct, pentru orice u V, u r, exist r-u drum n T. Vrful r se numete rdcina arborelui direcionat T (drumurile snt unice, rdcina este unic; lungimea unui drum este egal cu numrul de arce).

Definiie. Fie T = ( V, E ) arbore direcionat. Arborele T1 = (V1 ,E1 ) este subarbore al lui T dac V1 V, E1 E i T1 este arbore direcionat.

Structuri arborescenteArbore direcionatArbore direcionat cu rdcin

Reprezentri i parcurgeri (arbori orientai)Definiie. Un arbore orientat este un arbore direcionat cu rdcin.

Definiie. Fie T=(V,E), un arbore orientat cu rdcin r. Un vrf v este situat pe nivelul i al arborelui T, dac distana de la vrf la rdcin este egal cu i. Rdcina arborelui este considerat de nivel 0.

Se pot folosi toate tipurile de reprezentare a grafurilor, plus metode specifice arborilor, mai eficiente.

Reprezentarea Fiu-FrateN: numrul de noduriR: nodul rdcinFIU(i): numrul ataat primului descendent al vrfului i FRATE(i): numrul ataat vrfului descendent al tatlui vrfului i i care urmeaz imediat lui iINF(i): informaia ataat vrfului i de obicei informaia e chiar valoarea i, caz n care vectorul nu mai e necesarValoare lips: se folosete o valoare convenional (0, -1)

Reprezentarea Fiu-Frate 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 FIU =(2,5,0,8,0,9,0,14, 0, 0, 0, 0, 0, 0, 0, 0)FRATE =(0,3,4,0,6,7,0, 0,10,11,12,13, 0,15,16, 0) N = 16, R = 1Putem afla tatl unui nod?Putem afla descendenii unui nod?

Reprezentare folosind structuri dinamicePresupunnd c fiecare vrf al arborelui are cel mult n descendeni, fiecrui vrf i este ataat structura,

identificator vrfvector de legturi ctre descendenii vrfuluiadres fiu 1adres fiu n

ParcurgeriAplicarea sistematic a unei reguli de vizitare a vrfurilor arborelui. Cele mai utilizate reguli de parcurgere a arborilor orientai snt A-preordine (variant DF)A-postordine (variant DF)parcurgerea pe niveluri (BF)

Parcurgerea n A-preordine (Fiu-Frate)Este vizitat vrful curent i snt identificai descendenii lui. Se aplic aceeai regul de vizitare pentru fiecare dintre arborii avnd ca rdcini descendenii vrfului curent

void A_preordine (nod R){ if (R){ vizit (R); A_preordine(FIU[R]); A_preordine(FRATE[R]); }} 1, 2, 5, 6, 9, 10, 11, 12, 13, 7, 3, 4, 8, 14, 15, 16

Parcurgerea n A-postordine (Fiu-Frate)Se identific i se viziteaz descendenii vrfului curent, apoi se viziteaz vrful curent. Se aplic aceeai regul de vizitare pentru arborii avnd ca rdcini descendenii vrfului curent

void A_postordine (nod R){ if (R){ A_postordine(FIU[R]); vizit (R); A_postordine(FRATE[R]); }} 5, 9, 10, 11, 12, 13, 6, 7, 2, 3, 14, 15, 16, 8, 4, 1

Parcurgeri n adncime (str. dinamice)void A_preordine (nod R){ if (R) { vizit (R); for(i=0;ileg[i]); }}

void A_postordine (nod R){ if (R) { for(i=0;ileg[i]); vizit (R); }}

Parcurgerea pe niveluri (Fiu-Frate)void parcurgere_pe_niveluri(nod R, int FIU[], int FRATE[], int n){ TNOD* C = NULL; push(C,R); while (C) { pop(C,v); VIZIT(v); v=FIU[v]; while (v) { push(C,v); v=FRATE[v]; } }}1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Parcurgerea pe niveluri (str. dinamice)void parcurgere_pe_niveluri(nod *R){ TNOD* C = NULL; push(C,R); while (C) { pop(C,v); VIZIT(v); for(i=0;ileg[i]) push(C,R->leg[i]); }}

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Arbori pariali Definiie. Fie G un graf. Subgraful parial H este un arbore parial al lui G dac H este graf arbore.

Definiie. Fie G=(V,E,w) un graf ponderat conex. Dac T=(V,E0) este un arbore parial al grafului G=(V,E), ponderea arborelui T, notat W(T), este definit prin W(T)=

Definiie. Arborele parial T0T(G) este arbore parial minim pentru G dac W(T0) = min { W(T); TT(G) }, unde T(G) este mulimea arborilor pariali corespunztori grafului G.

Arbori parialiP = 22P = 20P = 15

Algoritmul lui KruskalProblem: determinarea arborelui parial de cost minimAlgoritm:E se iniializeaz arborele ca mulime vidDintre arcele disponibile (neselectate anterior) se alege arcul cu ponderea cea mai mic i care nu formeaz un ciclu prin adugare la arboreRepet pasul anterior de n 1 ori

Algoritmul lui Kruskal2 3 11 6 22 4 21 5 33 4 41 2 4 4 6 85 6 83 6 93 5 120 0 (2,3) (-1, -2, 2, -1, -1, -1) 1 1Nr. arc curentNr. arce selectateArc curentVectorul Tatav

Algoritmul lui KruskalFuncie pentru determinarea rdcinii

int radacina(int v,int tata[]){ int u = v; while(tata[u] >= 0) u = tata[u]; return u; }Ex.: v = 4u = 4 tata[4]=2u = 2 tata[2]=1u = 1 tata[1]=-6 < 0

1 2 3 4 5 6(-6, 1, 2, 2, 1, 1)

Algoritmul lui Kruskalint kruskal(int a[][3],int nm, int nv, int b[][3]){ int tata[50],i,j, v1, v2, r1, r2; int c=0; for(i=0; i

Spor la nvat!