Heap

Arbori

Definiție

 Numim arbore un graf neorientat conex si fără cicluri.

Proprietăți ale arborilor

Teorema 1

 Fie G=(V,U) un graf neorientat. Următoarele afirmații sunt echivalente:
- G este arbore
- Oricare două vârfuri din G sunt unite printr-un lanț simplu unic
- G este conex minimal (dacă suprimăm o muchie, graful obținut este neconex)
- G este conex si are |V|-1 muchii
- G este aciclic si are |V|-1 muchii
- G este aciclic maximal (dacă adăugăm o muchie, graful obținut conține cicluri)

Noțiuni Introductive

  1. Arbori
  2. Arbori binari
  3. Heap-uri

Generator Heap

Heap

  1. Creare
  2. Inserare nod
  3. Combinare
  4. Extragere nod

Coadă cu prioritate

Aplicații

Dicționar

Teorema 2

 Numerele întregi 0 <=d1 <= d2 <= ... <= dn (n>=2) sunt gradele vârfurilor unui arbore dacă și numai dacă d1+d2+...+dn = 2*n-2.

Arbori cu rădăcină

Definiție

 Un arbore cu radăcina este o mulțime finită de noduri care fie este vidă fie:
- există un nod special numit rădăcina arborelui
- mulțimea celorlalte noduri este partiționată în n>=0 clase A1, A2, ..., An, fiecare clasă fiind un arbore cu rădăcină. Rădăcina arborelui este unită prin muchii de rădăcinile arborilor A1, A2, ..., An.