popolarità degli alberi in informatica:

• strutture dati di frequente impiego negli algoritmi, v. ad es. quelli studiati per il problema della connettività
• le dinamiche di algoritmi hanno spesso struttura ad albero, ad es. invocazioni ricorsive in un algoritmo divide et impera

gli alberi sono inoltre presenti in una miriade di applicazioni: alberi genealogici, organigrammi, strutture di file system, strutture di libri, alberi sintattici, termini, ...

• cos'è, esattamente, un albero? ecco un paio di definizioni, per cominciare:

albero libero: grafo connesso privo di cicli

• N.B. equivalentemente: grafo in cui esiste esattamente un cammino fra ogni coppia di vertici

albero (radicato): albero con un vertice designato, detto radice

• N.B. sebbene il grafo di un albero sia generalmente non orientato, la designazione di un vertice radice induce naturalmente (per induzione) un ordinamento parziale dei vertici, grazie all'assenza di cicli, dunque un orientamento degli archi

cammino:
sequenza di vertici distinti, con vertici successivi connessi da archi

ordinamento dei vertici:

• m < n se m precede n nel cammino dalla radice a n

terminologia: padre, figli, foglie, sottoalbero, ...

un albero è k-ario se ogni vertice ha al più al più k figli

un albero k-ario è completo se ogni vertice interno (cioè non foglia) ha k figli

un albero si dice ordinato se è definito un ordine (totale) sui figli di ciascun padre

• i termini hanno struttura ad albero ordinato

l'altezza di un albero è la massima lunghezza (in n. di archi) dei cammini dalla radice

• è detta anche profondità dell'albero

la rappresentazione vista degli alberi binari ben si presta ad operazioni su di essi per l'esecuzione delle quali si proceda dalla radice verso le foglie

• altrimenti, si può estendere la struttura con un terzo link, che punta al vertice padre

la suddetta rappresentazione si generalizza facilmente ad alberi k-ari, dotando di k link la struttura di rappresentazione dei vertici, oltre all'eventuale link al vertice padre, quando ciò convenga

in tutti questi casi, si può anche scegliere una rappresentazione basata su array e indici invece di strutture e puntatori, poiché è prefissato un limite massimo al numero dei figli di qualsiasi vertice

• come rappresentare alberi in cui tale limite non c'è?

una soluzione consiste nel rappresentare l'insieme (ordinato o meno) dei figli di un vertice interno mediante una lista

• questa soluzione ci riporta ad una struttura con due soli link, come nel caso degli alberi binari...

qui, però, un link punta al figlio più a sinistra, l'altro punta a un fratello del vertice

• questa rappresentazione stabilisce una corrispondenza biunivoca fra alberi binari ordinati e foreste ordinate, v. esercizio 1

una foresta è un insieme di alberi che non condividono vertici

una foresta è ordinata se tale insieme è totalmente ordinato e gli alberi sono ordinati

gli alberi liberi sono grafi (non orientati) che soddisfano una proprietà caratteristica; questa può essere enunciata in vari modi: un grafo con N vertici è un albero libero se soddisfa una delle seguenti condizioni equivalenti:

• è connesso e privo di cicli
• ha N-1 archi ed è privo di cicli
• ha N-1 archi ed è connesso
• esiste esattamente un cammino (semplice) fra ogni coppia di vertici distinti
• è minimamente connesso, cioè è connesso, ma l'eliminazione di un qualsiasi arco lo rende non connesso

un cammino in un grafo è una sequenza di vertici in cui vertici successivi sono connessi da un arco: il cammino è semplice se ogni vertice in esso occorre una sola volta

• una foresta libera è un grafo in cui ogni cammino è semplice

ogni cammino è semplice anche in un albero libero, caso particolare di foresta libera

• analogamente a quanto visto per gli alberi liberi, è possibile fornire caratterizzazioni equivalenti del concetto di foresta libera, v. esercizio 2

1. dimostrare che esiste una biiezione fra alberi binari ordinati e foreste ordinate
2. generalizzare la caratterizzazione degli alberi liberi qui data da cinque condizioni equivalenti sui grafi, ad una analoga caratterizzazione delle foreste libere
3. su N vertici si possono costruire N^N-2 alberi liberi: quanti alberi radicati?
   • quanto asserito è stato dimostrato da Cayley nell'800; a Prüfer (1918) si deve un'elegante dimostrazione algoritmica: http://www.mathworld.wolfram.com/PrueferCode.html (v. anche nota EWD677 di E.W. Dijkstra)
4. due alberi (ordinati o meno) sono isomorfi se esiste una biiezione fra i vertici che rispetta la relazione binaria costituita dagli archi
   • cioè: se φ è una tale corrispondenza, ε₁ la relazione di esistenza di arco nel primo albero e ε₂ quella nel secondo albero, allora u ε₁ v ⇔ φ(u) ε₂ φ(v) per qualsiasi coppia di vertici u, v nel primo albero
   dimostrare che se due alberi ordinati rappresentano lo stesso albero non ordinato allora sono isomorfi, ma che non vale l'implicazione conversa
5. progettare e implementare un algoritmo per stabilire se due alberi ordinati, rappresentati da alberi binari ordinati come indicato qui, rappresentino lo stesso albero non ordinato, e valutarne le prestazioni sia in via analitica che empirica