Arborele (grafic)

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Un copac etichetat cu șapte vârfuri și șase căi.

În teoria graficelor , un copac este un grafic nedirecționat în care oricare două vârfuri sunt conectate printr-o singură cale (grafic nedirectat, conectat și fără buclă).

O pădure este, de asemenea, definită ca un grafic nedirecționat în care oricare două vârfuri sunt conectate de cel mult o cale (un grafic nedirectat fără cicluri). O pădure este alcătuită dintr-o uniune disjunctă de copaci (iar această proprietate își justifică numele); acești copaci constituie componentele sale maxime conectate.

Definiții

Un grafic G conectat, nedirecționat și fără buclă G se numește copac . Pentru a fi astfel, graficul trebuie să îndeplinească cel puțin una dintre următoarele cerințe:

  • Având o singură cale pentru fiecare pereche de vârfuri.
  • Fiind aciclic maxim , adică dacă adăugați o altă margine pentru a uni două dintre nodurile sale, se formează un ciclu.
  • Constituiți un grafic minim conectat, adică dacă eliminați una dintre muchiile sale, pierdeți conexiunea.

Dacă G are un număr finit de n vârfuri, enunțurile precedente sunt echivalente cu următoarele două:

  • G este conectat și are n - 1 margini.
  • G este aciclic (fără cicluri) și are n - 1 margini.

Un copac poate fi definit ca un grafic conectat astfel încât, eliminând oricare dintre muchiile sale, conexiunea se pierde. Prin urmare, un arbore poate fi apreciat ca un grafic conectat ieftin, deoarece menține conexiunea utilizând numărul minim posibil de margini.

Un copac poate fi apoi definit ca un grafic aciclic astfel încât adăugarea unei margini între două dintre nodurile sale care nu sunt conectate direct introduce în mod necesar un ciclu. Prin urmare, un copac poate fi apreciat ca un grafic aciclic cu cel mai mare număr posibil de conexiuni.

Având în vedere un grafic nedirecționat G = (V, E) definim un copac întins al lui G ca un copac T = (V ', E') astfel încât V '= V și E' este un subset al lui E. Dacă G nu este conectat un astfel de copac nu există.

O pădure este definită ca un grafic aciclic neorientat. Setul de păduri include în mod corespunzător setul de copaci, deoarece pădurile conectate sunt copaci și există păduri neconectate (ușor de identificat). Într-o pădure, pe lângă orice noduri izolate, există cu siguranță noduri de valență 1 care se numesc noduri în așteptare : de fapt, luând orice nod q, dacă identificați o cale care începe în q încercând să o extindem progresiv, la un anumit nivel indică că întâlnește un nod de valență 1, pentru că altfel s-ar construi un ciclu, împotriva naturii aciclice a pădurilor. Prin urmare, există un nod agățat într-un copac. Dacă ștergeți un astfel de nod și marginea care îl taie, veți obține totuși un copac, deoarece păstrați conexiunea și aciclicitatea acestuia.

Procedând cu aceste eliminări, trebuie să ajungem la un grafic nod.

Graficul nodului format dintr-un nod și fără margine este un copac (și, de asemenea, o pădure).

Gradul unui nod este numărul de copii sau subarburi ai unui nod.

Nivel

Nivelul unui nod dintr-un copac este egal cu 1 plus nivelul nodului părinte, ceea ce înseamnă că rădăcina are nivelul 0. De exemplu, un nod copil al rădăcinii va fi nivelul 1, copilul său va fi nivelul 2.

Înălţime

Înălțimea unui copac este maximul nivelurilor tuturor nodurilor sale.

Fiecare copac binar cu k frunze are o înălțime mai mare sau egală cu

Demonstrație

Procedând prin inducție asupra numărului k de frunze ale arborelui considerat avem că dacă k = 1 proprietatea este verificată în mod banal ( de fapt, dacă există o singură frunză, arborele este compus dintr-o singură rădăcină și, prin urmare, înălțimea, așa cum este definită, va fi 0). Să presupunem că proprietatea este adevărată pentru orice j astfel încât și ia în considerare un arbore binar T cu k frunze de înălțime minimă. Fie T 1 și T 2 cele două subarburi ale căror rădăcini sunt copiii rădăcinii lui T. Se observă că fiecare dintre acestea are mai puține frunze între cele două și are cel puțin k / 2 (în cazul unui număr par) . Apoi, prin ipoteza inducției, înălțimea acesteia din urmă este mai mare sau egală cu de aceea și înălțimea lui T este cu siguranță mai mare sau egală cu .

Lungimea drumului

Lungimea căii interne a unui arbore binar este dată de suma nivelurilor nodurilor interne, în timp ce lungimea căii externe a unui arbore binar este dată de suma nivelurilor nodurilor externe.

Clase de izomorfism

Arborii (sau mai bine zis clasele de izomorfism al arborilor) pot fi așadar aranjați pe diferite niveluri caracterizate prin numărul n al nodurilor lor. La nivelul 1 există graficul nodului, la nivelul 2 calea a 2 noduri, la nivelul 3 calea cu trei noduri, la nivelul 4 calea cu 4 noduri și steaua cu 3 puncte și așa mai departe. La nivelul n există toți și numai arborii cu margini n-1 care, cu procesul de reducere văzut mai sus, sunt reduși la graficul nodului cu n-1 pași în care numărul de margini scade cu unul.

În acest moment se dovedește că un copac cu n noduri are n-1 margini. În schimb, se poate arăta că un grafic conectat cu n noduri și n-1 margini este aciclic și, prin urmare, este un copac. Dar se poate arăta, de asemenea, că un grafic aciclic cu n noduri și n-1 margini este conectat și, prin urmare, este un copac.

Îmbogățirea copacilor

Un copac cu rădăcină este un copac îmbogățit de unul dintre vârfurile sale. O astfel de structură este echivalentă cu o arborescență, un digraf care are un vârf, rădăcina , din care se poate ajunge la fiecare dintre celelalte printr-o singură cale. Este, de asemenea, echivalent cu un contraarbor, digraf astfel încât are un vârf, numit dolină , la care poate fi atins fiecare de celelalte printr-o singură cale. De fapt, într-un copac înrădăcinat este posibil să se orienteze toate marginile în așa fel încât să se îndepărteze sau să se apropie de nodul privilegiat.

Arborii înrădăcinați sunt structuri de date folosite pe scară largă și strategice în informatică. Adesea sunt utile îmbogățiri suplimentare ale copacilor înrădăcinați: în special structurile pentru care este stabilită o ordine între vârfurile adiacente unui vârf dat (a se vedea structura de date a arborelui ). Un copac etichetat este un copac ale cărui vârfuri sunt prevăzute cu o etichetă care le distinge. Adesea etichetele atribuite unui copac cu rădăcină și n vârfuri sunt numerele întregi de la 1 la n.

Exemplu

Exemplu de copac.

Exemplul arborelui prezentat în dreapta are 6 vârfuri și 6 - 1 = 5 margini. Singura cale simplă care leagă vârfurile 2 și 6 este 2-4-5-6.

Proprietate

  • Fiecare grafic conectat G admite un subarborel care se întinde , adică un subgraf care este un copac și care conține toate vârfurile lui G.
  • Dat fiind n vârfuri marcate (și distincte), există n n −2 modalități diferite de a le conecta pentru a le transforma într-un copac. Acest rezultat se numește formula Cayley .
  • Numărul de copaci cu n vârfuri de grad d 1 , d 2 , ..., d n este

Aceasta se numește coeficientul multinomial .

  • Nu există o expresie închisă cunoscută pentru numărul t ( n ) al copacilor abstracte cu n vârfuri, adică numărul claselor de izomorfism al copacilor. Cu toate acestea, comportamentul asimptotic al lui t ( n ) este cunoscut: există două numere α ≈ 3 e

β ≈ 0,5 astfel încât

.
  • Orice copac cu un număr mai mare sau egal cu 2 noduri are cel puțin două frunze.
  • Fiecare copac cu n noduri are n-1 laturi. (Prin teorema lui Cayley )
  • Există o singură cale între orice pereche de noduri.
  • Dacă luăm în considerare un arbore de sprijin și graficul său de apartenență, adăugând arborelui o latură care nu îi aparține, dar care aparține graficului, se creează un singur ciclu.

Proprietăți binare ale arborelui

Concentrându-ne pe copacii binari există numeroase proprietăți matematice care sunt recurente în analiza algoritmilor .

 Un arbore binar cu N noduri interne are N + 1 noduri externe. 

Această proprietate poate fi dovedită prin inducție. Un arbore binar fără noduri interne are un nod extern, deci proprietatea este valabilă pentru N = 0. Pentru N> 0, orice arbore binar cu N noduri interne are nodul intern în subarborele drept și N-1-k în subarborele stâng, rădăcina fiind un nod intern. Prin inducție, subarborele stâng are k + 1 noduri externe, în timp ce dreapta are Nk pentru un total de N + 1.

 Un arbore binar cu N noduri interne are 2N margini: N-1 margini interne și N + 1 margini externe. 

În fiecare copac înrădăcinat, fiecare nod are un singur părinte și fiecare arc conectează un nod la părintele nodului. Deci, există N-1 arcuri care conectează noduri interne. În mod similar, fiecare dintre nodurile exterioare N + 1 are un arc îndreptat spre singurul părinte. Performanța multor algoritmi depinde nu numai de numărul de noduri ale arborelui asociat, ci și de diferitele proprietăți structurale ale acestuia.

Tipuri de copaci

Schema clasică a graficului arborescent utilizată pentru a descrie ierarhia dintre un râu (ordinul 1 ) și afluenții și subafluenții acestuia.

Arborele cu rădăcină

Un copac înrădăcinat este o pereche (T, r) unde T este un copac și r vârful său, care se numește rădăcină. Un copac înrădăcinat este, prin urmare, un copac în care este evidențiat un vârf (rădăcina); mai este numit copac înrădăcinat . Acum, având în vedere un vârf x într-un copac cu rădăcină r, există o singură cale simplă (r, V2, V3, ... V m , x) de la rax (dacă r este diferit de x); vârful V m care precede vârful x se numește tatăl lui x.

Arborele îngrijit

Un copac ordonat (numit și plan) este un copac înrădăcinat în care copiii fiecărui vârf sunt total ordonați.

Un copil rădăcină cu descendenții săi formează la rândul său un copac ordonat. Acest fapt permite să se dea următoarea definiție inductivă a unui arbore ordonat: k (definit pe seturi de vârfuri disjuncte) și r este un nod diferit de nodurile lui T 1 , T 2 , ... Tm apoi secvența (r, T 1 , T 2 , ..., T m ) este un copac ordonat.

Arborele binar

Un copac binar este un copac înrădăcinat în care fiecare nod intern are cel mult doi copii; fiecare copil se distinge ca un copil stâng sau drept copil. Următorii doi copaci sunt coincidenți ca arbori ordonați, dar distincti ca arbori binari:

Având în vedere un vârf x al unui arbore binar T, subarborele înrădăcinat în copilul stâng al lui x dacă există va fi numit subarborele stâng al lui x.

Catarg complet de înălțime h

Un copac binar complet este un copac binar în care fiecare nivel, cu excepția eventuală a ultimului, este complet plin și toate nodurile sunt cât mai departe în stânga posibil. Un copac este numit un copac aproape complet dacă ultimul nivel nu este complet plin. Acest tip de copac este folosit ca o structură de date specializată numită heap.

Numărul vârfurilor unui copac binar complet se dovedește a fi:

prin urmare

Din aceasta putem deduce că copacii complet conțin un număr mare de noduri cu o înălțime mică.

Arborescențe

Dacă luați un copac și evidențiați unul dintre nodurile sale, adică dacă îmbogățiți informațiile care identifică un copac cu semnalizarea unuia dintre nodurile sale, veți obține o structură ușor diferită, dar substanțial mai bogată. Aceasta ar trebui să fie numită arborescență și să o considere un digraf, deoarece marginile arborelui original pot fi orientate astfel încât să existe o cale orientată care duce de la nodul privilegiat la orice alt nod.

Tipul de structură astfel obținut este adesea numit specie de copaci cu rădăcină (copaci înrădăcinați). Acest termen este utilizat pe scară largă în informatică .

În acest sens, trebuie remarcat faptul că în aplicații arborescențele arborilor sunt mai necesare, într-adevăr sunt necesare arborescențe îmbogățite cu alte informații: acest lucru se întâmplă, de exemplu. cu arbori sintactici gestionați de compilatori sau în lingvistică și cu organigrame ierarhice asemănătoare copacilor. Apoi se întâmplă ca în anumite zone de aplicație termenul de copac să fie folosit pentru a indica o arborescență dotată cu anumite alte informații. Pe de altă parte, atunci când faceți matematică, este recomandabil să respectați definiții precise, posibil standard.

Pe de altă parte, în contextul anumitor sectoare, utilizarea necorespunzătoare (pentru matematică) a termenului arboresc poate fi acceptată, cu condiția să fie considerat un termen de argou, de utilizare limitată și justificabil prin convenții care pot să nu fie explicite, dar explicite și cu condiția să existe conștientizarea posibilității unor neînțelegeri inerente utilizării pripite a termenilor.

Elemente conexe

Alte proiecte

Controlul autorității LCCN (EN) sh85137259 · GND (DE) 4004849-4
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică