Grafuri de tip arbore

Grafuri de tip arbore

? ???

Graful este arbore dacă este aciclic şi conex.


11

22

33

44 55

66 77

88

99

G1G1

11

22

33

44 55

66 77

88

99

G2G2

11

22

33

44 55

66 77

88

99

G3G3

11

22

33

44 55

66 77

88

99

G4G4

Fie un graf arbore. Subgraful al lui este subarbore dacă este de tip arbore.


11

22

33

44 55

66 77

88

99

GG

55

66 77

88

99

H3H322

44 55

66 77

88

99

H2H2

11

22

33

44 55

66 77

88

99

H1H1

Fie un graf. Următoarele afirmații sînt echivalente:

G este graf arbore (aciclic şi conex); G este graf conex minimal G este graf aciclic maximal

Cum verificăm dacă un graf este arbore?

Verificare conexitate + verificare aciclicitate (alg. Marimont) Verificare aciclicitate şi n = m + 1 Verificare conexitate şi n = m + 1


11

22

33

44 55

66 77

88

99

GG

Fie un digraf Digraful este graf asimetric dacă pentru orice , . Digraful este graf simetric dacă pentru orice şi .


11

22

33

4455

66

77

D1D1

11

22

33

4455

66

77

D2D2

Fie un digraf netrivial Graful unde

se numește graf suport al digrafului .


11

22

33

4455

66

77

GG

11

22

33

4455

66

77

DD

Un arbore direcţionat este un graf orientat asimetric pentru care graful suport corespunzător este graf arbore.

Arborele direcţionat este arbore cu rădăcină dacă există astfel încît, pentru orice , , există drum în . Vîrful se numeşte rădăcina arborelui direcţionat (drumurile sînt unice, rădăcina este unică; lungimea unui drum este egală cu numărul de arce).

Fie arbore direcţionat. Arborele este subarbore al lui dacă , şi este arbore direcţionat.

Un arbore orientat este un arbore direcţionat cu rădăcină.

Fie , un arbore orientat cu rădăcină r. Un vîrf v este situat pe nivelul i al arborelui T, dacă distanţa de la vîrf la rădăcină este egală cu i. Rădăcina arborelui este considerată de nivel 0.



22

11

33

44

55 66

77

88

99

G1G1

1010

22

11

33

44

55 66

77

88

99

G2G2

1010

22

11

33

44

55 66

77

88

99

GSGS

1010

22

11

33

44

55 66

77

88

99

1010

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

Reprezentarea Fiu-Frate N: numărul de noduri R: nodul rădăcină Fiu(i): eticheta ataşată primului descendent al vîrfului i Frate(i): eticheta ataşată vîrfului descendent al tatălui vîrfului i şi care

urmează imediat lui i Inf(i): informaţia ataşată vîrfului i Valoare lipsă: se foloseşte o valoare convenţională (0, -1…)

Reprezentări

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

Cum se determină descendenții unui nod?

Cum se determină părintele unui nod?

Cum se adaugă un nod în arbore?

Reprezentări

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

Reprezentarea cu structuri dinamice Număr limitat de descendenți pentru fiecare nod: are valoare mică Pentru fiecare vîrf se alocă dinamic o structură de tipul

Pentru a cunoaște arborele: adresa nodului rădăcină

Reprezentări

Identificator vîrf

Informații vîrf Adresa fiu 1

Adrese descendenți

Adresa fiu 2 Adresa fiu n...

1 ? Adresa fiu 1

Adresa fiu 2

Adresa fiu 3 Null Null

Adresa nod rădăcină

2 ? Adresa fiu 1

Adresa fiu 2

Adresa fiu 3 Null Null 3 ? Null Null Null Null Null 4 ? Adresa

fiu 1 Null Null Null Null

5 ? Null Null Null Null Null

6 ? Adresa fiu 1

Adresa fiu 2

Adresa fiu 3

Adresa fiu 4

Adresa fiu 5

7 ? Null Null Null Null Null 8 ? Adresa fiu 1

Adresa fiu 2

Adresa fiu 3 Null Null




9 ? Null Null Null Null Null99





Aplicarea sistematică a unei reguli de vizitare a nodurilor arborelui

Variante adaptate ale parcurgerii grafurilor:

În lățime (BF)▪ Parcurgere pe niveluri

În adîncime (DF)▪ Parcurgerea în A-preordine▪ Parcurgerea în A-postordine

Parcurgeri

Pe niveluri (reprezentare Fiu-Frate)

parcurgere_pe_niveluri( R, FIU[], FRATE[], n ){ Coadă C = NULL; adaugă ( C, R ); cît timp ( C ) { extrage( C, v ); Prelucrează( v ); v = FIU[v]; cît timp ( v ) { adaugă( C, v); v = FRATE[v]; } }} 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Parcurgeri

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

Pe niveluri (reprezentare cu structuri dinamice)

parcurgere_pe_niveluri( R ){ Coadă C = NULL; adaugă ( C, R ); cît timp ( C ) { extrage( C, v ); Prelucrează( v ); pentru ( i=0,n-1 ) dacă ( v->fiu[i]) adaugă( C, v->fiu[i]); }} 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Parcurgeri

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

A-preordine (reprezentare Fiu-Frate) Se vizitează nodul curent și se identifică descendenții săi. Se aplică aceeași regulă, pe rînd,

pentru fiecare din subarborii care au ca rădăcină unul din descendenții nodului curent.

A_preordine ( R ){ dacă ( R ) { Prelucrează ( 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

Parcurgeri

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

A-postordine (reprezentare Fiu-Frate) Se identifică descendenții nodului curent și se vizitează, pe rînd, fiecare din subarborii care au

ca rădăcină unul din descendenții nodului curent, apoi se vizitează nodul curent. Pentru fiecare subarbore se aplică aceeași regulă.

A_postordine ( R ){ dacă ( R ) { A_postordine( FIU[R] ); Prelucrează ( R ); A_postordine( FRATE[R] ); }}

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

Parcurgeri

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

Parcurgeri în adîncime (reprezentare cu structuri dinamice)

A_preordine ( R ){ dacă( R ) { Prelucrează( R ); pentru( i=0,n-1) A_preordine( R->fiu[i] ); }}

A_postordine ( R ){ dacă(R) { pentru( i=0,n-1 ) A_postordine( R->fiu[i] ); Prelucrează( R ); }}

Parcurgeri

11

22 33 44

6655 77 88

1111 12121010 131399 15151414 1616

Fie un graf. Subgraful parţial este un arbore parţial al lui dacă este graf arbore.

Fie un graf ponderat conex. Dacă este un arbore parţial al grafului , ponderea arborelui , notată , este definită prin

Arborele parţial este arbore parţial minim pentru dacă

unde este mulţimea arborilor parţiali corespunzători grafului .

Arbori parțiali

Arbori parțiali

11

22

33

4455

66

77

2

4

3

3

2

1

6

3

GG2

35

11

22

33

4455

66

77

4

3

3

2

1T1T15

W(T1)=18W(T1)=18

11

22

33

4455

66

77

3

1

6T2T2

2

35

W(T2)=20W(T2)=20

11

22

33

4455

66

77

2

32

1

6

3

T3T3W(T3)=17W(T3)=17

Problemă

determinarea arborelui parţial de cost minim al grafului

Algoritm:

se iniţializează ca mulţime vidă

Repetă de ori

▪ Dintre arcele disponibile (care nu au fost analizate încă) se alege arcul cu

ponderea cea mai mică şi care nu formează un ciclu prin adăugare la

arbore.

Algoritmul lui Kruskal

i j arc Tata: 1 2 3 4 5 6 7 cost total ( -1 -1 -1 -1 -1 -1 -1 ) 00 1 (6,7) ( -1 -1 -1 -1 -1 7 -2 ) 1 11 2 (2,5) ( -1 5 -1 -1 -2 7 -2 ) 2 32 3 (2,7) ( -1 5 -1 -1 7 7 -4 ) 2 53 4 (4,5) ( -1 5 -1 7 7 7 -5 ) 2 74 5 (1,2) ( 7 5 -1 7 7 7 -6 ) 3 105 5 (1,4) ( 7 7 -1 7 7 7 -6 ) 106 6 (3,5) ( 7 7 7 7 7 7 -7 ) 3 13


11

22

33

4455

66

77

2

4

3

3

2

1

6

3

GG2

35

11

22

33

4455

66

77

TT

6 7 12 5 22 7 24 5 21 2 31 4 33 5 33 7 3 3 4 44 6 55 6 6

1

2

2

2

3

3

Pas curent

Nr. arce adăugate

Funcţie pentru determinarea rădăcinii

int radacina( int v, int tata[]){ int u; u = v; while( tata[u] >= 0 )

u = tata[u]; return u; }

Ex.: v = 2u = 2 tata[2]=5u = 5 tata[5]=7u = 7 tata[7]=-4 < 0


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

int 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<nv; i++) tata[i]=-1; for(i=j=0; j<nv-1; i++) { v1=a[i][0]; v2=a[i][1]; r1=radacina(v1,tata); r2=radacina(v2,tata); if( r1 != r2 ) { if( tata[r1] < tata[r2] ) { tata[r1]+=tata[r2]; tata[r2]=r1; } else { tata[r2]+=tata[r1]; tata[r1]=r2; }

b[j][0]=a[i][0]; b[j][1]=a[i][1]; b[j][2]=a[i][2]; c+=a[i][2]; j++; } } return c;}


Problemă

determinarea arborelui parţial de cost minim al grafului

Algoritm:

se iniţializează ca mulţime vidă

Alege un vîrf inițial oarecare , ,

Repetă de ori

▪ Alege muchia cu cea mai mică pondere a.î. și

Algoritmul lui Prim

Temă: Implementați algoritmul Prim Prim sau Kruskal?

Algoritmul lui Prim

11

22

33

4455

66

77

2

4

3

3

2

1

6

3

GG2

35

44552

22

2

772

661

11

3

33

3

Spor la învățat!

Grafuri de tip arbore

Documents

Transcript of Grafuri de tip arbore