Arborele (teoria graficelor)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 iunie 2020; verificările necesită 6 modificări .

Un arbore este un graf aciclic conex . [1] Conectivitatea înseamnă prezența unei rute între orice pereche de vârfuri, aciclicitatea înseamnă absența ciclurilor. Din aceasta, în special, rezultă că numărul de muchii dintr-un arbore este cu unul mai mic decât numărul de vârfuri și există una și o singură cale între orice pereche de vârfuri.

Pădurea este o mulțime de copaci.

Un arbore direcționat (direcționat) este un digraf aciclic ( un grafic direcționat care nu conține cicluri), în care doar un vârf are un grad de intrare zero (nu există arce în el), iar toate celelalte vârfuri au un grad de intrare de 1 (exact un arc duce la ele). Un vârf cu grad zero de intrare se numește rădăcina arborelui, vârfurile cu grad zero de rezultat (din care nu iese niciun arc) sunt numite vârfuri terminale sau frunze . [2]

Definiții înrudite

Gradul unui vârf este numărul de muchii incidente cu acesta.

Un nod de capăt ( frunză , vârf terminal ) este un nod cu gradul 1 (adică un nod la care duce doar o margine; în cazul unui arbore direcționat, un nod la care duce doar un arc și nu iese niciun arc) .

Un nod de ramură este un nod non-terminal.

Un copac cu un vârf marcat se numește arbore înrădăcinat .
- $m$ Nivelul al treilea al arborelui este setul de noduri de arbore, la nivelul de la rădăcina arborelui. $T$ $m$
- ordine parțială pe vârfuri: dacă vârfurile și sunt diferite și vârful se află pe lanțul elementar (unic!) care leagă rădăcina cu vârful . $u\precv$ $u$ $v$ $u$ $v$
- subarbore rădăcină înrădăcinat ca subgraf . $v$ $\{v\}\cup \{w\mid v<w\}$
- Într-un context în care se presupune că un copac are o rădăcină, se spune că un copac fără o rădăcină distinctă este liber .

Nivelul nodului - lungimea căii de la rădăcină la nod. Poate fi definit recursiv:

nivelul rădăcinii arborelui este 0; $T$
nivelul oricărui alt nod este cu unul mai mare decât nivelul rădăcinii celui mai apropiat subarboresc al arborelui care conține acel nod. $T$

Un arbore de întindere ( schelet ) este un subgraf al unui grafic dat care conține toate vârfurile sale și este un arbore. Marginile graficului care nu sunt incluse în schelet se numesc coarde ale graficului în raport cu scheletul.

Un arbore se numește ireductibil dacă nu are vârfuri de gradul 2.

O pădure este o mulțime (de obicei ordonată) care nu conține un singur arbore care nu se intersectează sau conține mai mulți arbori care nu se intersectează.
Centroid - un vârf, la îndepărtarea căruia dimensiunile componentelor conectate rezultate nu depășesc (jumătate din dimensiunea arborelui original) ${\dfrac {n}{2)}$

Arborele binar

Termenul de arbore binar (este folosit și termenul de arbore binar) are mai multe semnificații:

Un arbore nedirecționat cu grade de vârf de cel mult 3.
Un arbore direcționat în care gradele de ieșire ale vârfurilor (numărul de muchii de ieșire) nu depășesc 2.
O structură de date abstractă utilizată în programare . Structurile de date precum arborele de căutare binar , heap binar , arbore roșu-negru , arbore AVL , heap Fibonacci etc. se bazează pe un arbore binar.

Arbori N-ari

Arborii N-ari sunt definiți prin analogie cu un arbore binar. De asemenea, au cazuri direcționate și nedirecționate, precum și structuri de date abstracte corespunzătoare.

Un arbore N-ary (nedirecționat) este un arbore (obișnuit, nedirecționat) în care gradele vârfurilor nu depășesc N + 1.
Un arbore N-ary (direcționat) este un arbore direcționat în care gradele de ieșire ale vârfurilor (numărul de muchii de ieșire) nu depășesc N.

Proprietăți

Arborele nu are margini sau bucle multiple .
Orice arbore cu vârfuri conține o margine. Mai mult, un graf conex finit este un arbore dacă și numai dacă , unde este numărul de vârfuri și este numărul de muchii ale graficului. $n$ $n-1$ $BP=1$ $B$ $P$
Un graf este un arbore dacă și numai dacă oricare dintre vârfurile sale distincte pot fi conectate printr-un singur lanț simplu .
Orice arbore este determinat în mod unic de distanțele (lungimea celui mai mic lanț) dintre vârfurile sale terminale (gradul 1).
Orice arbore este un grafic bipartit .
Orice arbore al cărui set de vârfuri este cel mult numărabil este un graf plan .
Pentru oricare trei vârfuri arborescente, căile dintre perechile acestor vârfuri au exact un vârf comun.

Numărarea copacilor

Numărul de arbori diferiți care pot fi construiți pe vârfuri numerotate este ( teorema lui Cayley [3] ). $n$ $n^{{n-2}}$
Funcția generatoare

T(z)=\sum _{n=1}^{\infty }T_{n}z^{n}

pentru numărul de arbori înrădăcinați neizomorfi cu vârfuri satisface ecuația funcțională

T_{n}

n

T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})

Funcția generatoare

t(z)=\sum _{n=1}^{\infty }t_{n}z^{n}

pentru numărul de arbori neizomorfi cu vârfuri poate fi reprezentat folosind seria de listare pentru arbori înrădăcinați:

t_{n}

n

t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\dreapta).

Pentru următoarele asimptotice este adevărat $n\la\infty$

t_{n}\sim C\alpha ^{n}/n^{5/2}

unde și sunt anumite constante, , .

C

\alfa

C=0,534948...

\alpha =2,95576...

Codarea arborelui

Un arbore poate fi codificat ca seturi de zerouri și unu. Luați în considerare, de exemplu, așezarea unui copac pe un avion. Pornind de la un vârf, ne vom deplasa de-a lungul marginilor arborelui, întorcându-ne la fiecare vârf până la marginea cea mai apropiată din dreapta și întorcându-ne înapoi la vârfurile de capăt ale arborelui. Trecând de-a lungul unei margini, scriem când ne mișcăm de-a lungul marginii pentru prima dată și când ne deplasăm de-a lungul marginii a doua oară (în direcția opusă). Dacă este numărul de muchii ale arborelui, atunci după pași vom reveni la vârful inițial, trecând prin fiecare muchie de două ori. Secvența rezultată de lungimi și (codul arborelui) face posibilă restabilirea fără ambiguitate nu numai a arborelui în sine , ci și a așezării acestuia pe plan. Un arbore arbitrar corespunde mai multor astfel de coduri. În special, următoarea estimare aproximativă pentru numărul de arbori cu vârfuri rezultă din această metodă de codificare: $0$ $unu$ $m$ $2m$ $0$ $unu$ $2m$ $D$ $n$ $t_{n}\leq T_{n}<2^{2n}$

Codul Prufer mapează la un arbore finit arbitrar cu vârfuri o secvență de numere de la până la cu posibile repetări. De exemplu, arborele din figură are codul Prufer (4,4,4,5). Există o corespondență unu-la-unu între arborii de vârf etichetați și codurile lor Prufer. Formula lui Cayley este derivată din codul Prüfer . $n$ $n-2$ $unu$ $n$

Arborele poate fi specificat ca un șir care conține caractere care marchează nodurile arborelui, precum și paranteze de deschidere și de închidere. Există o corespondență unu-la-unu între arbori și notațiile lor liniare.

Vezi și

Glosar al teoriei grafurilor
Pădurea de mulțimi disjuncte
Lista structurilor de date (arbori)

Note

↑ § 13. Definiția unui arbore // Prelegeri despre teoria grafurilor / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - P. 53. - 384 p. — 22.000 de exemplare. — ISBN 5-02-013992-0 .
↑ Alfs Berztiss. Capitolul 3. Teoria grafurilor. 3.6. Arbori // Structuri de date = AT Berztiss. structuri de date. teorie și practică. - M. : Statistică, 1974. - S. 131. - 10.500 exemplare.
↑ Matematică discretă: algoritmi. Formula lui Cayley (link inaccesibil) . Consultat la 29 octombrie 2009. Arhivat din original pe 14 iunie 2009. (nedefinit)

Literatură

Donald Knuth . Arta programarii computerelor, vol. 1. Algoritmi fundamentali. - Ed. a 3-a. - M .: Williams , 2006. - T. 1. Algoritmi de bază. — 720 s. - ISBN 0-201-89683-4 .
Ore O. Teoria grafurilor. - Ed. a II-a. — M .: Nauka , 1980. — 336 p.
Harari F. Teoria grafurilor. — M .: Mir , 1973. — 302 p.

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree