https://www.algopedia.ro/wiki/index.php?action=history&feed=atom&title=Clasa_a_XI-a_lec%C8%9Bia_29 2026-04-15T10:40:25Z Revision history for this page on the wiki MediaWiki 1.44.2 https://www.algopedia.ro/wiki/index.php?title=Clasa_a_XI-a_lec%C8%9Bia_29&diff=16284&oldid=prev 2019-05-27T21:57:09Z

<p><span class="autocomment">Arbore liber</span></p> <p><b>New page</b></p><div>= Arbori =<br /> ==Arbore liber==<br /> Un arbore este un graf conex și aciclic. Se mai numește și arbore liber.<br /> <br /> [[Image:arbore-liber.png]]<br /> <br /> Următoarele propoziții sunt adevărate:<br /> <br /> Un arbore cu n vârfuri are n-1 muchii.<br /> Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex.<br /> Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, s-ar obține un ciclu.<br /> Între oricare două vârfuri ale unui arbore există un lanț elementar unic.<br /> <br /> ==Arbore radacina==<br /> Pentru un arbore se poate stabilii un nod special, numit rădăcină. Putem spune că “agățăm” arborele în rădăcină, iar restul nodurilor cad.<br /> <br /> Mai jos avem trei arbori cu rădăcină. Toți pornesc de la arborele de mai sus, dar diferă prin alegerea rădăcinii.<br /> <br /> [[Image:arbore-radacina2.png]][[Image:arbore-radacina3.png]][[Image:arbore-radacina4.png]]<br /> <br /> ===Terminologie===<br /> Fie un arbore cu rădăcina r și x un nod în acest arbore. atunci:<br /> <br /> *se numește ascendent al lui x orice nod y aflat pe lanțul de la rădăcină la x.<br /> rădăcina nu are ascendenți<br /> rădăcina este ascendent pentru toate nodurile din arbore<br /> *dacă y este ascendent al lui x și există muchia (y,x), atunci y se numește ascendent direct al lui x sau tatăl lui x<br /> rădăcina este singurul nod din arbore care nu are tată<br /> *un nod y este descendent al nodului x dacă x aparține lanțului de la r la y<br /> dacă în plus există muchia (x,y), atunci y este descendent direct sau fiu al lui x<br /> un nod care nu are niciun descendent se numește frunză<br /> *două noduri care au același tată se numesc frați<br /> *lungimea unui lanț de la rădăcina arborelui la un nod x reprezintă nivelul sau adâncimea nodului x<br /> *lungimea maximă a unui lanț de la rădăcină la un nod al arborelui reprezintă înălțimea arborelui<br /> *un nod al arborelui împreună cu toți descendenții săi formează un subarbore<br /> [[Image:arbore-radacina.png]]</div>

Bella