Arbori

Definitia 1: Se numeste Arbore cu rădacină = graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Descendent direct / fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.

Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului y dacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.

Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.

Frunză = într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent direct

Arbore cu rădăcină

- Nodul 1 este rădăcină. - Nodurile 5, 6, 7 sunt fii nodului 3. - Nodul 7 este părintele nodurilor 9 şi 10; - Nodul 9 este descendentul lui 3 - Nodul 3 este ascendentul lui 10 - Nodurile 8, 9 şi 10 sunt frunze - Nodurile 5, 6 şi 7 sunt fraţi.

Metode de memorare a arborilor

Cum un arbore este un caz particular de graf neorientat inseamna ca poate fi reprezentat ca un graf. De aici rezulta ca pentru reprezentarea unui arbore se pot utiliza:

1. Metode specifice grafurilor:

-matricea de adiacenta

-liste de adiacente

2. Metode specifice arborilor:

-prin legaturi de tip TATA. Arborele se reprezinta sub forma unui vector t cu n componente (n reprezinta numarul de noduri). Daca t[i]=k atunci nodul I este descendent al nodului k. Daca nodul I este varf atunci t[i]=0.

Fie arboreal din figura:

unde nodul 1 este radacina. Atunci vectorul de tip tata este:

0

1

1

1

3

3

3

4

7

7

Legatura de tip TATA se mai numeste si legatura cu referinte ascendente.

Legatura de tip TATA este determinata si de modul in care am ales nodul radacina. Spre exemplu daca vom considera nodul 4 ca fiind radacina vom obtine o alta solutie.

Metode de parcurgere:

Metodele de parcurgere sunt cele specifice grafurilor: in adancime si in latime.

Probleme propuse:

· Pornind de la definitia arborelui: un graf neorientat care este conex sin nu contine cicluri sa se determine daca un graf neorientat este arbore. Graful este memorat prin matricea de adiacente. Solutie

· Definitia 2 – un graf neorientat cu n noduri care are n-1 muchii si nu contine cicluri. Pornind de la definitia 2 sa se determine daca un graf neorientat memorat prin matricea de adiacente poate fi arbore.

· Fie arborele din figura anterioara. Sa se reprezinte arborele prin: matricea de adiacenta, liste de adiacenta. Sa se memoreze arborele prin legatura de tip TATA, considerand nodul 1 radacina si apoi nodul 4 radacina

· Fie un arbore memorat prin matricea de adiacenta. Sa se treaca arborele in vector de tip tata. Se citeste radacina. Solutie

· Dintr-un fisier se citesc : numarul de noduri apoi vectorul de tip tata.
a) sa se determine radacina
b) afisati frunzele (nodurile terminale)
c) pentru un nod citit sa se determine: fii si parintele
d) sa se determine nodul cu cei mai multi descendenti

· Arbore genealogic. Dintr-un fisier se citesc numele a n persoane. Persoanele sunt numerotate de la 1 la n. In continuare se citesc m perechi de nume x y cu semnificatia x este parintele lui y. Sa se determine:

a) stramosul comun

b) persoanele fara descendenti

c) parintele unei persoane al carei nume se citeste de la tastatura

d) fii unei persoane al carei nume se citeste de la tastatura

e) daca doua personae al caror nume se citesc de la tastatura sunt frati

f) toti ascendentii unei personae

g) toti descendentii unei persoane

h) sa se determine bunicul unei persoane

i) se citesc numele a doua persoane x,y. Sa se determine daca x este ascendentul lui y (direct sau indirect)

j) din a cata generatie face parte o persoana citita?

k) Cate generatii are arborele

l) verii unei persoane

· Sa se memoreze intr-un arbore numere intregi (prin legaturi de tip tata) .

o Sa se determine lantul simplu radacina-frunza avand cea mai mare suma a cifrelor

o Sa se determine lantul simplu radacina-frunza avand cele mai multe numere prime

· In mod evident numarul de niveluri al unui arbore depinde de radacina aleasa. Dandu-se un graf conex si fara cicluri sa se determine un nod care sa fie radacina astfel incat numarul de niveluri sa fie maxim (minim).

· Se citesc doi arbori, unde fiecare are nodurile 1,2,…,n si sunt reprezentati prin legaturi de tip tata. Sa se decida daca ei reprezinta unul si acelasi arbore (in reprezentari diferite).

· Sa se afiseze nodurile unui arbore pe niveluri

· Fie doi arbori reprezentati prin vectorii de tati. Sa se determine daca cei doi arbori reprezinta unul si acelasi graf.