Arbori – cele mai simple grafuri
Din punct de vedere structural, cele mai simple grafuri sunt cele numite ARBORI. Acestea sunt , de fapt, si cele mai folosite in practica. De-a lungul timpului, de studiul arborilor s-au ocupat matematicieni si fizicieni de prima marime.
Trebuie observat ca organizarea de tip lista liniara nu este totdeauna cea mai adecvata in unele aplicatii. Astfel, daca trebuie descrisa structura unui produs, aceasta nu se face descriindu-i componentele una cate una, ci se apeleaza la o descriere ierarhica a partilor care il compun, adica o structura asemanatoare unui arbore. Organizarea ierarhica este intalnita in cele mai diverse domenii, de la organizarea administrativa a unei tari, la planificarea meciurilor unui meci sportiv, de la structurarea unei carti, pana la stabilirea ordinii de executie a operatiilor efectuate pentru determinarea valorii unei expresii aritmetice.
De exemplu, cataloagele in care sunt sunt grupate fisierele de pe discurile fixe sau flexibile au o structura ierarhica. Aceasta organizare este impusa in principal de ratiuni de gestionare cat mai comoda a fisierelor de diverse tipuri apartinand diversilor utilizatori ai aceluiasi sistem de calcul si exemplele pot continua. Generalizand, intr-o varianta sistemica, orice entitate din natura sau societate poate fi reprezentata ca un tot sau ca o ierarhie de componente.
Pentru varfurile unui arbore se va folosi termenul nod. Figurativ o structura de tip arbore arata ca un arbore, in inteles general dar este rasturnat. Fiecare element din aceasta structura poate fi privit ca o radacina de la care pornesc ramuri catre radacinile altor arbori. In reprezentarea grafica a unui arbore nodurile se deseneaza pe niveluri astfel: radacina se afla pe primul nivel, varfurile adiacente cu radacina pe urmatorul nivel, s.a.m.d.
O prima definitie intuitiva a structurii de arbore este urmatoarea: un arbore A este fie vid fie format dintr-un nod radacina (R) caruia ii este atasat un numar finit de arbori. Acestia sunt denumiti subarbori ai lui A datorita relatiei de subordonare fata de radacina. Deci intr-un arbore, orice nod este radacina unui subarbore, iar orice arbore poate fi sau poate deveni subarbore. Intre doi subarbori nu poate exista decat o relatie de incluziune (unul este subarbore al celuilalt) sau de excluziune ( cei doi arbori nu au noduri comune dar apartin aceluiasi arbore). Multi termeni folositi in studiul arborilor sunt imprumutati din terminologia utilizata in cazul arborilor genealogici sau din natura. Astfel pentru a desemna o relatie directa intre doua noduri se folosesc termenii: tata, fiu, frate, cu semnificatia obisnuita. Pentru relatiile indirecte, de tipul fiul fiului … fiului, se folosesc termenii descendent sau urmas si respectiv ascendent sau stramos. Nodurile fara descendenti sunt anumite noduri terminale sau prin analogie cu arborii din natura, frunze.
Accesul de la radacina unui arbore nevid la oricare alt nod presupune parcurgerea unei cai formate din a arce (a 0) pe care se gasesc q noduri (q=a+1) valoarea q reprezinta nivelul pe care se gaseste nodul fata de radacina, acesta fiind considerata prin conventie pe nivelul zero.
Inaltimea unui arbore se poate defini ca maximul dintre nivelurile nodurilor terminale, sau o alta definitie recursiva: Inaltimea unui arbore este egal cu unu plus maximul dintre inaltimile subarborilor sai. Numarul de descendenti directi ai unui nod reprezinta ordinul nodului. In cazul in care ordinul nodurilor nu este delimitat, arborele este denumit arbore multicai.
Definitia 24: Daca fiecare dintre nodurile unui arbore are cel mult 2 descendenti directi, atunci arborele se numeste arbore binar . Intr-un arbore binar nevid, cei doi potentiali subarbori sunt subarbore stang si subarbore drept.
Obs.: Orice arbore multicai poate fi privit ca un arbore binar, daca orice nod este considerat in relatie directa cu cel mult alte doua noduri: primul fiu si urmatorul frate. De foarte multe ori este referata folosirea arborilor binari in locul arborilor multicai.
Definitia 25: un graf conex si fara cicluri se numeste ARBORE.
Teorema: pentru un graf G =(X,U) cu n 2 noduri, m muchii si p componente conexe, urmatoarele afirmatii sunt echivalente si caracterizeaza un arbore:
G este conex si fara cicluri;
G este fara cicluri si m=n-1;
G este conex si m=n-1;
G este un graf fara cicluri, maxima (daca se adauga o muchie intre doua noduri neadiacente, se formeaza un ciclu si numai unul);
G este un graf conex, minimal(daca se elimina o muchie oarecare, se obtine un graf care nu mai este conex);
Orice pereche de noduri este legata de un lant si numai unul.
|
