arbore

un arbore este un grafic neorientat G care îndeplinește oricare dintre următoarele condiții echivalente:

• G este conectat și aciclic (nu conține cicluri).
• G este aciclic și se formează un ciclu simplu dacă se adaugă o margine la G.
• G este conectat, dar ar deveni deconectat dacă o singură margine este îndepărtată din G.
• G este conectat și graficul complet cu 3 noduri K3 nu este un minor al lui G.
• orice două vârfuri din G pot fi conectate printr-o cale simplă unică.

Dacă G are finit multe vârfuri, să zicem n dintre ele, atunci afirmațiile de mai sus sunt, de asemenea, echivalente cu oricare dintre următoarele condiții:

• G este conectat și are N − 1 muchii.
• G este conectat și fiecare subgraf al lui G include cel puțin un vârf cu zero sau o muchie incidentă. (Adică G este conectat și 1-degenerat.)
• G nu are cicluri simple și are margini n-1.

ca și în alte părți ale teoriei grafurilor, graficul de ordine-zero (grafic fără vârfuri) nu este în general considerat a fi un copac: deși este conectat vid ca un grafic (oricare două vârfuri pot fi conectate printr-o cale), nu este conectat 0 (sau chiar (-1)-conectat) în topologia algebrică, spre deosebire de copacii care nu sunt goi și încalcă relația „încă un vârf decât marginile”. Cu toate acestea, poate fi considerată o pădure formată din zero copaci.

un nod intern (sau nod interior sau vârf de ramură) este un nod de grad cel puțin 2. În mod similar, un vârf extern (sau vârf exterior, vârf terminal sau frunză) este un vârf de gradul 1.

un arbore ireductibil (sau arbore redus în serie) este un copac în care nu există un vârf de gradul 2 (enumerat la secvența a000014 în OEIS).

ForestEdit

o pădure este un grafic neorientat în care oricare două vârfuri sunt conectate prin cel mult o cale. În mod echivalent, o pădure este un grafic aciclic nedirecționat, ale cărui componente conectate sunt copaci; cu alte cuvinte, graficul constă dintr-o uniune disjunctă de copaci. Ca cazuri speciale, graficul ordine-zero (o pădure formată din zero copaci), un singur copac și un grafic fără margini, sunt exemple de păduri.Deoarece pentru fiecare copac V-E = 1, putem număra cu ușurință numărul de copaci care se află într-o pădure scăzând diferența dintre vârfurile totale și marginile totale. TV-TE = Numărul de copaci într-o pădure.

PolytreeEdit

un polytree (sau copac direcționat sau copac orientat sau rețea conectată individual) este un grafic aciclic direcționat (DAG) al cărui grafic neorientat subiacent este un copac. Cu alte cuvinte, dacă înlocuim marginile sale direcționate cu margini neorientate, obținem un grafic neorientat care este atât conectat, cât și aciclic.

unii autori restricționează expresia „arbore direcționat” la cazul în care marginile sunt toate direcționate către un anumit vârf sau toate direcționate departe de un anumit vârf (vezi arborescență).

Poliforestedit

o poliforest (sau pădure direcționată sau pădure orientată) este un grafic aciclic direcționat al cărui grafic neorientat subiacent este o pădure. Cu alte cuvinte, dacă înlocuim marginile sale direcționate cu margini neorientate, obținem un grafic neorientat care este aciclic.

unii autori restricționează expresia „pădure direcționată” la cazul în care marginile fiecărei componente conectate sunt toate direcționate către un anumit vârf sau toate direcționate departe de un anumit vârf (vezi ramificare).

copac înrădăcinat

un copac înrădăcinat este un copac în care un nod a fost desemnat rădăcină. Marginilor unui copac înrădăcinat i se poate atribui o orientare naturală, fie departe, fie spre rădăcină, caz în care structura devine un copac înrădăcinat direcționat. Când un copac înrădăcinat direcționat are o orientare departe de rădăcină, se numește arborescență sau copac; când are o orientare spre rădăcină, se numește anti-arborescență sau în copac. Ordinea arborelui este ordonarea parțială pe vârfurile unui copac cu u< v dacă și numai dacă calea unică de la rădăcină la v trece prin u. un arbore înrădăcinat T care este un subgraf al unui grafic G este un arbore normal dacă capetele fiecărei căi T în G sunt comparabile în această ordine a arborelui (Diestel 2005, p. 15). Copacii înrădăcinați, adesea cu structură suplimentară, cum ar fi ordonarea vecinilor la fiecare vârf, sunt o structură cheie de date în informatică; vezi structura datelor arborelui.

într-un context în care copacii ar trebui să aibă o rădăcină, un copac fără nicio rădăcină desemnată se numește copac liber.

un copac etichetat este un copac în care fiecărui nod i se dă o etichetă unică. Vârfurile unui arbore etichetat pe n vârfuri sunt de obicei date etichetele 1, 2,…, N. un copac recursiv este un copac înrădăcinat etichetat unde etichetele vârfului respectă ordinea arborelui (adică., dacă u < v pentru două vârfuri u și v, atunci eticheta u este mai mică decât eticheta v).

într-un copac înrădăcinat, părintele unui vârf v este vârful conectat la v pe calea către rădăcină; fiecare vârf are un părinte unic, cu excepția rădăcinii care nu are părinte. Un copil al unui vârf v este un vârf din care v este părintele. Un ascendent al unui vârf v este orice vârf care este fie părintele lui v, fie este (recursiv) Ascendentul părintelui lui v. Un descendent al unui vârf v este orice vârf care este fie copilul lui v, fie este (recursiv) descendentul oricăruia dintre copiii lui v. Un frate la un vârf v este orice alt vârf de pe copac care are același părinte ca v. o frunză este un vârf fără copii. Un nod intern este un nod care nu este o frunză.

înălțimea unui vârf într-un copac înrădăcinat este lungimea celei mai lungi căi descendente către o frunză din acel vârf. Înălțimea copacului este înălțimea rădăcinii. Adâncimea unui vârf este lungimea căii către rădăcina sa (calea rădăcinii). Acest lucru este necesar în mod obișnuit în manipularea diferiților arbori de auto-echilibrare, în special a copacilor AVL. Rădăcina are adâncimea zero, frunzele au înălțimea zero, iar un copac cu un singur vârf (deci atât rădăcină, cât și frunză) are adâncimea și înălțimea zero. În mod convențional, un copac gol (un copac fără vârfuri, dacă este permis) are adâncimea și înălțimea -1.

un copac k-ary este un copac înrădăcinat în care fiecare vârf are cel mult K copii. Copacii cu 2 ari sunt adesea numiți copaci binari, în timp ce copacii cu 3 ari sunt uneori numiți copaci ternari.

copac Ordonatedit

un copac ordonat (sau platan) este un copac înrădăcinat în care este specificată o ordonare pentru copiii fiecărui vârf. Aceasta se numește „planar”, deoarece o ordonare a copiilor este echivalentă cu o încorporare a copacului în plan, cu rădăcina în partea de sus și copiii fiecărui vârf mai mici decât acel vârf. Având în vedere o încorporare a unui copac înrădăcinat în plan, dacă se fixează o direcție a copiilor, să zicem de la stânga la dreapta, atunci o încorporare dă o ordonare a copiilor. În schimb, având în vedere un copac ordonat și desenarea convențională a rădăcinii în partea de sus, atunci vârfurile copilului dintr-un copac ordonat pot fi desenate de la stânga la dreapta, rezultând o încorporare plană esențial unică.