albero libero
albero libero
albero libero struttura matematica descrivibile come un insieme di nodi e un insieme di archi che uniscono coppie di nodi così da costituire un particolare tipo di → grafo (A), tali che:
a) A sia connesso, cioè esista un percorso semplice tra ogni coppia di nodi N′, N″ definito come un sottoinsieme ordinato di nodi distinti {N0, N1, ..., Ns-1, Ns}, dove N′ ≡ N0 e N″ ≡ Ns, tale che ogni coppia (Ni, Ni+1), con 0 ≤ i ≤ s − 1, sia unita da un arco;
b) A non contenga alcun ciclo, cioè un percorso semplice in cui i nodi iniziale e finale coincidono.
Si può verificare che per un albero libero A di n nodi:
• A contiene n − 1 archi;
• esiste un solo percorso semplice tra ogni coppia di nodi di A;
• se si rimuove un arco qualsiasi di A, la struttura risultante non è più connessa, ma risulta composta da due alberi liberi;
• la definizione di albero libero può essere riformulata sostituendo in questa la condizione a) o la condizione b) con la nuova condizione: A contiene n − 1 archi.
La denominazione di albero (libero) per questa struttura discende dall’analogia con l’elemento vegetale, una volta assegnato un opportuno ordinamento ai suoi nodi. Scelto, infatti, un nodo arbitrario di un albero libero come radice si possono ordinare i suoi nodi in livelli.
<ALBERO LIBERO : fig_lettA_00570_001.jpg>
<ALBERO LIBERO : fig_lettA_00570_002.jpg>