 |
|
 |  |
|
|
| |
 | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
| Istorie | Literatura | Matematica | Psihologie |
Scurt istoric al teoriei grafurilor
Jocurile si amuzamentele matematice au fost punctul de plecare a ceea ce numim astazi "teoria grafurilor". Dezvoltandu-se la inceput paralel cu algebra, aceasta ramura a stiintei a capatat in timp atat forma cat si continut propriu, devenind un tot unitar bine conturat si bine fundamentat teoretic, cu o larga aplicare practica.
Printre primii care s-au ocupat de acest domeniu au fost König si Berge. Acestia au stabilit primele notiuni de limbaj specific domeniului.
"Data nasterii" a teoriei grafurilor poate fi considerata anul 1736, cand matematicianul elvetian Leonard Euler a publicat in revista "Comentarii Academiae Scientiarum Imperiali Petropolitanae" un articol in limba latina.
Ca izvoare ale teoriei grafurilor mai pot fi considerate: fizica - studiul retelelor electrice, geografia - problema colorarii hartilor cu cel mult patru culori, chimia - principalul initiator fiind Cayley etc.
Bazandu-ne pe notiuni care astazi fac parte din domeniu teoriei grafurilor fizicianul Kirchoff a studiat retelele electrice contribuind in mod decisiv la dezvoltarea teoriei electricitatii in (in 1845 a formulat legile care guverneaza circulatia curentului intr-o retea electrica, iar in 1847 a aratat cum poate fi construita intr-un graf o multime fundamentala de cicluri).
Teoria grafurilor este o ramura destul de noua, a teoriei multimilor, care s-a dovedit foarte utila si cu aplicatii in domenii variate: economie, chimie organica, organizare, psihologie, anumite domenii ale artei etc. Grafurile ofera cele mai potrivite metode de a exprima relatii intre obiecte, de aceea aria lor de utilizare practica este foarte vasta, de la economie la psihologie sociala.
In scopul familiarizarii cu diversele domenii de aplicare, prezentam cateva probleme "clasice" a caror rezolvare implica notiuni legate de teoria grafurilor.
Se pune problema construirii unei sosele intre doua localitati notate cu 1 si respectiv 8, care ar putea sa treaca prin localitatile 2, . ,7. cunoscand costul lucrarii pentru fiecare dintre tronsoanelor ce lega doua localitati, astfel incat costul general al lucrarii sa fie cat mai mic.
Daca localitatile se figureaza prin puncte, iar portiunile de sosea prin curbe, se obtine figura , care este de asemenea un graf.
Trei muncitori trebuie sa fie repartizati sa lucreze pe trei masini. Se cunoaste randamentul fiecarui muncitor pe fiecare masina in parte si se doreste stabilirea unei repartizari a muncitorilor pe fiecare masina astfel incat sa se obtina un maxim de randament. Notand cu 1, 2 si 3 cei trei muncitori, cu a, b si c cele trei masini si cu linii drepte posibilitatile de asociere dintre fiecare muncitor si fiecare masina, se obtine reprezentarea sub forma unui graf. Evident, daca o legatura nu este trasata, inseamna ca muncitorul nu are calificarea necesara pentru a putea lucra pe masina respectiva.
Iesirea din labirint
Labirintele sunt constructii stravechi, primele referiri la ele intalnindu-se in mitologie. Mai tarziu s-au construit labirinte din garduri vii in gradinile si parcurile curtilor imperiale, pentru amuzament, dar si pentru frumusetea lor. Indiferent din ce materiale au fost construite, acestea presupun existenta unui numar de culoare separate intre ele, care se intalnesc in anumite puncte. Studiul lor, inceput la sfarsitul secolului XIX, a demonstrat ca unui labirint i se poate asocia un graf in care varfurile corespund intersectiilor, iar muchiile, culoarelor labirintului. O problema imediata ar fi aceea de a gasi iesirea din labirint, pornind dintr-un punct al sau, parcurgand un traseu care sa fie, eventual, cat mai scurt.
Problema protocolului
La un dineu oficial participa 2n persoane, fiecare dintre acestea avand printre invitati cel mult n-1 persoane cu care nu este in relatii de prietenie. Pentru reusita intalnirii, organizatorii trebuie sa aseze la masa fiecare persoana, astfel incat fiecare sa aiba ca vecini numai persoane cu care sa se aiba in relatii bune.
Problema datoriilor
Intr-un grup sunt mai multe persoane, care au unele fata de altele, diverse datorii. Pentru achitarea datoriilor, fiecare persoana poate plati sume datorate, urmand ca sa primeasca, la randul sau, sumele cuvenite de la datornici. Procesul se poate bloca daca exista persoane care nu dispun de intreaga suma pe care o datoreaza altora, desi suma pe care o poseda ar acoperii diferenta intre suma datorata si cea cuvenita. In cazul in care sumele disponibile sunt suficiente, ar trebui sa se stabileasca subgrupurile de persoane care au datorii reciproce, pentru reglementarea datoriilor in cadrul subgrupului.
In exemplele date, prin folosirea unor puncte si a unor legaturi intre acestea, figurate prin segmente, problemele din practica s-au transformat in probleme ce tin de teoria grafurilor.
2. Notiuni introductive.
Metode de reprezentare a grafurilor
Se considera multimile finite X= si multimea U, care este produsul cartezian al multimi X cu ea insasi.
Definitia 1: Se numeste graf o pereche ordonata de multimi (X,U), X fiind o multime finita si nevida de elemente numite varfuri sau noduri, iar U o multime de perechi (submultimi cu doua elemente) din X, numite muchii sau arce.
Multimea X se numeste multimea nodurilor sau varfurilor grafului, iar multimea U se numeste multimea muchiilor sau multimea arcelor.
Un graf va fi notat cu G=(X,U), iar in figura sa, varfurile (nodurile) se vor desena prin cifre sau litere, muchiile prin linii neorientate si arcele prin linii orientate.
Definitia 2: Se spune ca multimea U are proprietatea de simetrie daca si numai daca avand [Xi, Xk] Є U rezulta ca [Xk, Xi] I U.
Definitia 3: Daca multimea U are proprietatea de simetrie, se spune ca graful G=(X, U) este graf neorientat.
Pentru G=(X, U)graf neorientat, o muchie u se noteaza [Xi, Xk] si este o pereche neordonata de varfuri distincte din X (adica Xi, Xk I X si Xi ≠ Xk).
Varfurile Xi si Xk se numesc extremitatile muchiei u si se spune ca Xi si Xk sunt varfuri adiacente.
Daca un varf nu este extremitatea nici uni arc, atunci el se numeste varf izolat.
Considerand muchia u, notata [Xi, Xk], se spune ca varfurile Xi si Xk, sunt incidente cu muchia [Xi, Xk]. De asemenea, despre doua muchii care au o extremitate comuna se numesc incidente. Uneori, prin abuz de limbaj, se mai foloseste notatia [Xi,Xk] IU.
Definitia 4: Daca multimea U nu are proprietatea de simetrie, se spune ca graful G=(X,U) este graf orientat sau directionat sau digraf. Daca G=(X, U) este un graf orientat, muchiile se numesc arce; un arc u se noteaza cu [Xi, Xk] si este o pereche ordonata de varfuri distincte din X (adica Xi, Xk I X si Xi ≠ Xk).
Pentru un arc (Xi, Xk), Xi este numit baza arcului sau originea sau extremitatea initiala, iar Xk este numit varful arcului sau extremitatea finala sau terminala B.
Se spune ca Xk este adiacent lui Xi. Avand arcul (Xi, Xk), se mai spune ca acesta este incident spre exterior cu Xi si incident spre interior cu Xk. Daca un varf nu este nici extremitatea initiala, nici extremitatea finala a vrunui arc, atunci el se numeste varf izolat.
Definitia 5: Se considera graful G=(X, U). Daca U=Ř (multime vida), atunci graful G=(X, U) se numeste graf nul si reprezentarea lui in plan se reduce la figurarea unor puncte izolate.
Definitia 6: Se defineste gradul unui varf x al uni graf G=(X, U) ca fiind numarul muchiilor incidente cu x si se noteaza cu d(x).
Definitia 7: Daca un varf are gradul 0 (nu exista nici o muchie incidenta cu el), atunci el se numeste varf izolat, iar daca are gradul 1 (este incident cu o singura muchie) se numeste varf terminal.
Proprietatea 1: Fie graful G=(X, U) cu n varfuri x1, x2, . , xn si m muchii.
Atunci suma gradelor nodurilor grafurilor este 2m adica:
n
Σ d(Xk)=2m
k=1
Definitia 8: Fie graful G=(X, U) si V U
Graful Gp=(X, V) se numeste graf partial al grafului G=(X, U). se poate spune ca un graf partial se poate obtine pastrand toate nodurile, dar eliminand o parte din muchii. Daca V=U, atunci Gp coincide cu G.
Definitia 9: Fie graful G=(X, U). se numeste graf complementar al grafului G graful G'=(X, U') cu proprietatea ca doua varfuri sunt adiacente in G' daca ele nu sunt adiacente in G.
Definitia 10: Fie graful G=(X, U) si Y X. fie V U, unde V contine toate muchiile din U care au ambele extremitati in Y. graful H=(Y, V) se numeste subgraf al grafului G=(X, U).
Se spune ca subgraful H e indus sau generat de multimea de varfuri Y.
Definitia 11: Se considera U=X*XD. Atunci graful G=(X, U)se numeste graf complet si se noteaza Kn (n fiind numarul de varfuri ale grafului). D=
Definitia 12: Graful G=(X, U) se numeste bipartit daca exista doua multimi nevide A si B astfel incat x=A B, A B= si orice muchie u a lui are o extremitate in A si cealalta extremitate in B.
Definitia 13: Graful G=(X, U) bipartit se numeste bipartit complet daca in orice varf xi din A si orice varf xk din B exista muchia [xi, xk].
Metode de reprezentare
1. Lista de adiacente: aceasta metoda este indicata in cazul in care graful are un numar mare de noduri si un numar mic de muchii.
2. Matricea de adiacenta sau matricea asociata grafului G(X, U)
A= (aij) este definita astfel:
| 1, pentru (xi, xj) I U
Aij=|
| 0, in caz contrar
3. Parcurgerea grafurilor neorientate
Asa cum arata si denumirea, parcurgerea unui graf neorientat, indica posibilitatea de a ajunge o singura data in fiecare varf al grafului, pornind de la un varf dat xk si parcurgand muchii adiacente. Aceasta operatiune poarta numele de vizitare sau traversare a varfurilor si este efectuata cu scopul prelucrarii informatiei asociata varfurilor.
Deoarece graful este o structura neliniara de organizare a datelor, prin parcurgerea sa, in mod sistematic se realizeaza si o aranjare lineara a varfurilor sale, deci informatiile stocate in varfuri se pot regasi si prelucra mai usor.
Pentru a facilita scrierea, convenim ca in lc de sa se scrie , fora ca valabilitatea rezultatelor sa fie diminuata. Astfel, prin similitudine, se poate folosii drept relatie de ordine intre varfurile grafului, relatia de ordine din numerele naturale (notata cu "<").
Cele mai cunoscute metode de parcurgere a unui graf sunt parcurgerea BF ("in latime") si parcurgerea DF ("in adancime") fiind prezentate in continuare .
1. Metoda de parcurgere BF (Breath First - "in latime"). Se viziteaza intai varful initial, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora, s.a.m.d.
Vizitarea unui varf inseamna de fapt o anumita prelucrare specificata asupra varfului respectiv, insa in acest moment este importanta intelegerea problemelor legate de parcurgerea unui graf prin metoda BF, deci se va insista doar asupra acestui aspect.
Derularea algoritmului presupune alegerea, la un moment dat, dintre toti vecinii unui varf, pe acela ce nu a fost vizitat. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiunea n, ale carui componente se definesc astfel:
pentru ∀k: 1, daca varful k a fost vizitat
VIZITAT[k] =
0, in caz contrar.
Se foloseste o structura de tip coada (simulata in alegerea statica printr-un vector V) in care prelucrarea unui varf aflat la un capat al cozii (varful cozii) consta in introducerea in celalalt capat al ei (coada cozii) a tuturor varfurilor j vecine cu k, nevizitate, inca. Evident, pentru inceput, k este egal cu varful indicat initial i si toate componentele lui VIZITAT sunt zero.
Algoritmul consta in urmatorii pasi:
Pasul 1. Se prelucreaza varful initial k:
Pasul 1.1 Se adauga varful k in coada;
Pasul 1.2 Varful k se considera vizitat
Pasul 2. Cat timp coda este nevida se executa:
Pasul 2.1 Pentru toti vecinii j nevizitati inca ai varfului k, executa:
Pasul 2.1.1 Se adauga varful j in coada; Pasul 2.1.2 Varful j se considera vizitat ;
Pasul 2.2 Se reia de la pasul 2.1
Se doreste parcurgerea sa incepand cu varful 1. s-a marcat cu linii punctate ordinea de vizitare a varfurilor. Pentru aceasta se executa pasii:
o Se adauga in coada vecinii sai(nevizitati):6; coada contine 1,2,3,4,5,6;
o Se trece pe nivelul urmator;
2.Metoda de parcurgere DF. (Deph First - "in adancime")
Parcurgerea unui graf in acest mod este o problema specifica metodei de rezolvare backtracking. Pentru rezolvarea practica a acestei probleme se foloseste un vector VIZITAT definit ca si la metoda BF; insa in locul cozii se va folosii o stiva (simulata in alocare statica printr-un vector V). astfel, in orice moment, exista posibilitatea de a ajunge de al varful curent la primul dintre vecinii sai nevizitati inca acesta fiind plasat in varful stivei. Cu acest varf se continua in acelasi mod. In vectorul URM se determina, la fiecare pas, urmatorul mod ce va fi vizitat dup nodul k (cand acesta exista). Pentru al determina, se parcurge linia k din matricea de adiacenta A asociata grafului, incepand cu urmatorul, pana se gaseste un vecin j al lui, nevizitat inca.
Daca este gasit, se incarca in varful stivei si se mareste corspunzator "pointerul de stiva" p. Daca sunt mai multi vecini, se alege acela care are cel mai mic numar de ordine (pentru ca denumirea de "radacina" sa aiba sens).
Daca nu se poate determina un astfel de varf, se coboara in stiva (p se micsoreaza cu 1), incercand sa aplicam procedeul urmatorului element al stivei.
Folosind o structura de tip stiva, prelucrarea unui varf aflat la un capat al stivei (varful stivei), consta in introducerea in acelasi capat al ei, a tuturor varfurilor j vecine cu k, nevizitate inca. Evident, pentru inceput, k este egal cu varful indicat initital i.
Algoritmul consta in urmatorii pasi:
Pasul 1. Se adauga varful k in stiva si se afiseaza;
Pasul 2. Se analizeaza varful k:
Pasul 2.1 Se cauta primul dintre vecini sai nevizitati, cu numar >k;
Pasul 2.1.1 Daca exista (fie acesta j), se adauga in stiva varful j si se afiseaza;
Pasul 2.1.2 Daca nu exista, se coboara in stiva; fie j continutul corespunzator al stivei;
Pasul 2.2 varful j devine varful ce trebuie analizat ;
Pasul 3. Cat timp stiva este nevida se executa pasul 2.
Se considera urmatorul graf:
➏
➑
Se doreste parcurgerea sa incepand cu varful 1. S-a
marcat cu sageti punctate ordinea de vizitare a varfurilor.
Pentru aceasta se executa pasii:
o se determina primul dintre vecinii sai: 2;
o se adauga in stiva varful 2, si se afiseaza ; stiva contine: 1,2;
o se determina primul dintre vecinii sai: 5;
o se adauga in stiva varful 5 si se afiseaza: stiva contine: 1,2,5;
o se determina primul dintre vecinii sai: 7;
o se adauga in stiva varful 7 si se afiseaza; stiva contine: 1,2,5,7;
o se cauta primul dintre vecinii sai nevizitati, cu numar >7;
o nu exista; se coboara in stiva; stiva contine: 1,2,5;
o se cauta primul dintre vecinii sai nevizitati, cu numar >5;
o nu exista; se coboara in stiva; stiva contine: 1,2;
o se cauta primul dintre vecinii sai nevizitati, cu numar >2;
o nu exista; se coboara in stiva; stiva contine: 1;
o se cauta primul dintre vecinii sai nevizitati, cu numar>1: 3;
o se adauga in stiva varful 3; se afiseaza varful 3; stiva contine: 1,3;
o se cauta primul dintre vecinii sai nevizitati, cu numarul>3: 6;
o se adauga in stiva varful 6; se afiseaza varful 6; stiva contine:1,3,6;
o se cauta primul dintre vecinii sai nevizitati, cu numar>6: 8;
o se adauga in stiva varful 8;se afiseaza varful 8; stiva contine: 1,3,6,8;
se analizeaza varful 8 (ca element curent al stivei):
o se cauta primul dintre vecinii sai nevizitati, cu numar>8;
o nu exista; se coboara in stiva; stiva contine:1,3,6;
se analizeaza varful 6 (ca element curent al stivei):
o se cauta primul dintre vecinii sai nevizitati, cu numarul>6;
o nu exista; se coboara in stiva; stiva contine: 1,3;
o se cauta primul dintre vecinii sai nevizitati cu numar>3;
o nu exista; se coboara in stiva; stiva contine: 1;
o se cauta primul dintre vecinii sai cu numar>1: 4;
o se adauga in stiva si se afiseaza; stiva contine:1,4;
o se cauta primul dintre vecinii sai nevizitati, cu numar>4;
o nu exista; se coboara in stiva; stiva contine:1,4;
o se cauta primul dintre vecinii sai nevizitati, cu numar>1;
o nu exista; se coboara in stiva; stiva este vida.
Succesiunea de varfuri afisata, 1,2,5,7,3,6,8,4 indica succesiunea de varfuri rezultata din parcurgerea acestui graf folosind metoda DF.
4. Conexitate
Definitia 14: Fie graful G=(X,U). numim lant o succesiune de varfuri L=[x1, x2, . ,xn] cu proprietatea ca oricare doua varfuri succesive sun adiacente, adica [x1,x2]IU, [x2,x3] IU, . ,[xp-1,xp] IU. varfurile x1 si xp se numesc extremitatile lantului, iar numarul de muchii ce il compun se numeste lungimea lantului.
Definitia 15: Daca varfurile x1,x2, . ,xp sunt distincte doua cate doua, lantul se numeste lant elementar. In caz contrar, lantul se numeste lant neelementar.
Definitia 16: Daca intr-un lant, toate muchiile sunt diferite intre ele, lantul se numeste simplu, in caz contrar lantul se numeste compus.
Definitia 17: Daca varfurile x1 si xp coincid, lantul se numeste ciclu. Daca un ciclu are o lungime para, el se numeste par; daca are o lungime impara, se numeste impar.
Definitia 18: Daca toate varfurile unui ciclu sunt distincte, cu exceptia primului si a ultimului, atunci ciclu se numeste ciclu elementar.
Definitia 19: Un graf se numeste conex daca oricare ar fi doua varfuri x si y, exista un lant ce le leaga.
5. Grafuri hamiltoniene
Definitia 20: Fie graful G(X,U). Daca exista un lant elementar care contine toate varfurile grafului, lantul se numeste lant hamiltonian.
Definitia 21: Daca intr-un lant hamiltonian varful initial si varful final coincid, lantul se numeste ciclu hamiltonian, iar graful ce contine un ciclu hamiltonian se numeste graf hamiltonian.
Termenul de ciclu hamiltonian a fost folosit pentru prima data in anul 1857 de William Hamilton, important matematician al epocii, inventatorul unui joc numit jocul icosian. Acesta consta in gasirea unui ciclu hamiltonian care sa uneasca cele 20 de varfuri ale unui dodecaedru, confectionat initial din lemn, cu cate un cui cu o floare la fiecare colt, deplasarea facandu-se numai pe muchii.
O problema devenita clasica ce foloseste notiunea de ciclu hamiltonian este aceea numita problema voiajorului comercial. Aceasta are urmatoarea formulare: "un comis voiajor trebuie sa-si prezinte produsele in mai multe orase. Cunoscand costul deplasarii intre localitatea, se doreste stabilirea unui traseu astfel incat sa ajunga in toate localitatile, insa costul calatoriei sa fie minim". Evident, fiecare localitate poate fi vizitata o singura data, iar la sfarsit, voiajorul comercial revine in punctul de plecare
Folosind termenii teoriei grafurilor, problema revine la determinarea unui ciclu hamiltonian in graful kn, ale carui varfuri reprezinta cele n localitatea, pentru care suma costurilor muchiilor sale este minima.
Pentru a stabili o legatura intre notiunile de graf complet si graf hamiltonian, prezentam urmatoarea teorema:
Teorema: Greful complet kn este hamiltonian.
Teorema: Daca graful G=(X,U) este un graf cu n 3 varfuri, astfel incat gradul fiecarui varf xIX satisface conditia:
d(x) n/2
atunci G este hamiltonian.
6. Grafuri euleriene
Definitia 22: Fie graful G=(X,U). daca exista un lant care contina toate muchiile grafului o singura data fiecare, lantul se numeste lant eulerian.
Definitia 23: Daca cele doua extremitati ale unui lant eulerian (varful initial si cel final) coincid, lantul devine ciclu eulerian, iar graful ce contine un ciclu eulerian se numeste graf eulerian.
Teorema: un graf G fara varfuri izolate este eulerian daca si numai daca este conex si gradul fiecarui varf este par.
7. Arbori
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.
8. Parcurgerea arborilor binari
Prin parcurgerea arborilor binari se intelege, ca si la glafurile obisnuite, examinarea in mod sistematic a nodurilor a.i. fiecare nod sa fie atins o singura data. Aceasta procedura se mai numeste si VIZITARE a nodurilor arborelui in scopul prelucrarii informatiei continute de fiecare dintre acestea.
Deoarece arborii sunt structuri neliniare de organizare a datelor, rolul traversarii este tocmai obtinerea unei aranjari liniare a nodurilor, pentru ca trecerea de la unul la altul sa se realizeze cat mai simplu posibil.
Analizand situatia la nivelul unui arbore binar, se observa ca pentru a avea parcurgere riguroasa dar mai ales eficienta, tebuie precizata in fiecare moment pozitia a trei componente, si anume: radacina si cei doi subarbori ai sai (stang si drept). Sunt deci 3!=6 variante. Pentru a facilita reprezentarea unui arbore binar se tine seama de urmatoarea regula: totdeauna este reprezentat subarborele stang si apoi subarborele drept. In raport de acestia, se pozitioneaza radacina. S-au obtinut astfel 3 posibilitati de reprezentare. Acestea sunt definite recursiv: daca arborele este vid, atunci el este traversat fara a executa nimic; daca nu este vid, atunci se executa pasii dintre cele trei modalitati de traversare:
(RDS) 1. Traversarea in preordine presupune:
Pasul 1 Se viziteaza radacina;
Pasul 2 Se treverseaza subarborele stang;
Pasul 3 Se treverseaza subarborele drept.
(SRD) 2. Traversarea in ordine presupune:
Pasul 1 Se treverseaza subarborele stang;
Pasul 2 Se viziteaza radacina;
Pasul 3 Se traverseaza subarborele drept;
(SDR) 3. Traversarea in postordine presupune:
Pasul 1 Se treverseaza subarborele stang;
Pasul 2 Se traverseaza subarborele drept;
Pasul 3 Se viziteaza radacina.
Observatie: Denumirea metodelor semnifica momentul cand se viziteaza radacina in raport cu vizitarea subarborilor (subarborele stang inainte celui drept in totdeauna).
Procedurile PASCAL de parcurgere a uni arbore binar prezentate in continuare aplica prima modalitate de prezentare a arborilor binari, adica folosesc cei doi vectori S si D pentru retinerea descendentilor stanga si respectiv dreapta ai fiecarui nod. Aceste programe, realizate folosind metoda de rezolvare DIVIDE ET IMPERA, sunt:
program parcurg_arbore;
uses crt;
var s,d: array[1..10] of byte;
rad, n, i, k: byte;
procedure RSD (k:byte);
begin
write (k, ' ');
if s[k]<> 0 then RSD (s[k]);
if d[k]<> 0 then RSD (d[k]);
end;
procedure SRD (k: byte);
begin
if s[k]<>0 then SRD(s[k]);
write (k, ' ');
if d[k]<>0 then SRD (d[k]);
end;
procedure SDR (k: byte);
begin
if s[k]<>0 then SDR (s[k]);
if d[k]<>0 then SDR (d[k]);
write(k, ' ');
end;
begin
clrscr;
write('Introduceti numarul de varfuri n: '); readln(n);
write ('Introduceti nodul radacina: '); readln(rad);
for i:=1 to n do
begin
writeln(' Pentru nodul ',I,' introduceti ');
write('descendent stang: '); read (s[i]);
write('descendent drept:'); read (d[i]);
end;
writeln;
writeln('*Parcurgere in preordine(RSD): ');
RSD(rad); writeln;
Writeln('*parcurgere in ordine(SRD): ');
SRD(rad); writeln;
Writeln('*Parcurgere in postordine (SDR) ');
SDR(rad); writeln;
Readln:
end
ANEXE
Copyright © 2024 - Toate drepturile rezervate
