Arbori

Se numește arbore un graf conex aciclic.
  • numărul nodurilor se notează în general cu n
  • numărul muchiilor se notează în general cu m

Un arbore cu n noduri are n-1 muchii.

Reprezentarea grafică a unui arbore

Arbore
    Pentru arborele G cu n muchii, sunt echivalente afirmațiile:
  • G este conex minimal;
  • G este aciclic maximal;
  • G este conex cu n-1 muchii;
  • G este aciclic cu n-1 muchii.

  Un arbore poate fi reprezentat ca arbore cu rădăcină; rădăcina corespunde nivelului 0.   Considerăm arborele anterior cu rădăcina în nodul 2:

Arbore cu radacina

  Pentru acest arbore cu rădăcina în 2 observăm că înălțimea sa este 2 (lungimea celui mai lung lanț elementar pornind din rădăcină).

Terminologie arbori

    Definim următorii termeni:
  1. Nod terminal = nod cu gradul 1 (rădăcină sau frunză);
  2. Frunză = nodurile terminale cu excepția rădăcinii („capetele” arborelui);
  3. Descendent = orice nod de pe nivelurile următoare ale subgrafului (o parte din arbore, cu rădăcina în nodul la care ne referim);
  4. Descendent direct = Fiu = orice nod de pe nivelul următor care se leagă direct, printr-o muchie, de nodul la care ne referim;
  5. Ascendent = orice nod de pe nivelurile anterioare ale ramurii pe care ne aflăm (ramura din arbore în care se află nodul de referință);
  6. Ascendent direct = Părinte (tată) = nodul de pe nivelul anterior de care este legat direct nodul la care ne referim;
  7. Frate = orice nod care are același ascendent direct (tată);

Exemple

    Folosind termenii descriși, să spunem cât mai multe despre nodul 3 din arborele de mai sus:
  • are 3 descendenți, toți fiind descendenți direcți;
  • este tată pentru 3 frunze;
  • are 4 frați, dintre care 3 sunt frunze;
  • are un singur ascendent, un nod terminal (rădăcina).

Pentru a obține arborele cu cea mai mare înălțime, vom căuta cel mai lung lanț elementar și vom alege una din extremități ca rădăcină. Pentru înalțimea minimă, vom alege un nod din mijlocul celui mai lung lanț elementar.