E’ un tipo speciale di grafo non orientato, connesso, aciclico e non vuoto.

In informatica sono molto utilizzati, per rappresentare strutture dati e algoritmi.

Terminologia

• Foresta, grado non orientato, aciclico e non vuoto. ogni componente connessa è un albero.
• Foglia, nodo in un albero con grado 1 (es. 1,3,4,5,7,9)
• Nodo interno, nodo con grado > 1
• Albero radicato, albero con un nodo speciale chiamato radice.

Proprietà

• Nodi:
  • Numero di nodi ? Es. è uguale a 10
  • Numero di archi? Es. è uguale a 9 archi

Tra gli archi e i nodi vige una regola stretta

• Path:
  • Numero di path tra due nodi? Es.1
  • Se tolgo un arco ? Il grafo diventa disconnesso
  • Se aggiungo un arco tra due nodi (Es. 4 e 8)? Creo un ciclo

Queste regole oltre all’esempio, valgono per tutti gli albero.

Proposizione