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 arbore este un grafic neorientat în care oricare două vârfuri sunt conectate printr-o singură cale (grafic nedirectat, conectat și fără cicluri).

De asemenea, definește pădurea un grafic nedirecționat în care oricare două vârfuri sunt conectate cel mult pentru a fi o cale (grafic nedirectat și lipsit de 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

Se spune că un grafic arborescent G conectat, nedirecționat și fără cicluri. 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 plafon aciclic , adică, dacă adăugați o altă margine pentru a îmbina două dintre nodurile sale, formați o buclă.
  • Constituiți un grafic conectat care este minim, dacă eliminați una dintre margini, conexiunea se pierde.

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ă.

Definește pădurea 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 extindă progresiv, la un anumit 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.

Nodul grafic este format dintr-un nod și fără margini ascuțite, este un copac (și, de asemenea, o pădure).

Se numește grad de nod al numărului 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ă. Dacă T 1 și T 2 cele două subarburi care au rădăcină pentru 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 numărului 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

Copacii (sau clase mai bune de izomorfism a copacilor) , atunci pot fi dispuse pe niveluri diferite caracterizate prin n numărul de noduri 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 sunt toți și numai arborii cu margini n-1 care, cu procesul de reducere văzut mai sus, sunt reduși la nodul grafic cu n-1 pași în care scade cu unu numărul de margini.

Î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

Spune copac înrădăcinat un copac decorat cu unul dintre vârfurile sale. O astfel de structură este echivalentă cu o structură de copac, un digraf care posedă un vârf, rădăcina, de la care fiecare dintre celelalte este accesibil printr-o singură cale. Este, de asemenea, echivalent cu un controarborescenza, un digraf care posedă un vârf, numit dolină, care este accesibil unul de altul 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, ele sunt utile pentru îmbogățirea suplimentară a copacilor înrădăcinați: în special, structurile pentru care stabilește o ordonare între vârfurile adiacente unui vârf dat (v. O structură de date a copacului ). Spune copac etichetat un copac ale cărui vârfuri sunt marcate cu o etichetă care le distinge. Adesea etichetele atribuite unui copac cu vârfurile sale rădăcină și n sunt numere î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 o acoperire sub arbore , adică un subgraf care este un copac și care conține toate vârfurile lui G.
  • Datele n nodurile marcate (și pot fi distinse), sunt n n-2 moduri diferite de a le conecta pentru a le transforma într - un copac. Acest rezultat se numește formula lui Cayley .
  • Numărul de copaci cu n vârfuri de grad d 1, d 2, ..., d n este

Aceasta se numește coeficient multinomial .

  • Nu se cunoaște nicio expresie care nu este închisă pentru numărul t (n) al copacilor abstracte cu n vârfuri, și anume numărul claselor de izomorfism al copacilor. Cu toate acestea, se cunoaște comportamentul asimptotic al lui t (n): există două numere α ≈ 3 și

β ≈ 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. (Pentru teorema 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ă multe 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

Diagrama clasică a arborelui grafic folosit pentru a descrie ierarhia dintre un râu (articolul 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 cale simplă unică (r, V2, V3, ... V m, x) de la rax (dacă r nu este egal cu x); V m vârf care precede vârful x se spune că tatăl.

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 arborelui ordonat: k (definit pe seturi disjuncte de vârfuri) er 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. 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ă. Acest lucru este de acord cu arborescența apelului și ia în considerare un digraf, deoarece marginile originale ale arborelui pot fi direcționate astfel încât să aibă o cale direcționată 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 adesea folosit î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 analizați tratați de compilatori sau limbă , și cu diagramele arborelui, ierarhic. Apoi se întâmplă ca în anumite domenii de aplicare să se utilizeze termenul de copac pentru a indica o structură de copac prevăzută 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ă