# Algoritmi/Grafi e alberi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario

## Grafi

G = (V, E):
* V = insieme finito dei vertici/nodi
* E = insieme finito di archi, che mette coppie di vertici in relazione (binaria)
* grafo non orientato: non esiste un verso di percorrenza
* grafo orientato: un arco può essere percorso in un solo verso
cappio = arco che ritorna sul vertice di partenza (solo nei grafi orientati)
Due vertici si dicono tra loro adiacenti se sono connessi da un arco.
grado di un vertice = numero di archi che insistono su quel vertice per i grafi orientati: in_degree (entranti), out_degree (uscenti)
Esiste un cammino tra due vertici se esiste una sequenza di vertici per cui il primo vertice è uguale a uno dei due vertici e l'ultimo è uguale all'altro vertice, e se esiste una sequenza di k archi.
cammino semplice = non ripassa mai su un nodo già passato → i vertici sono tutti distinti.
ciclo o cammino chiuso = il vertice di partenza e di arrivo coincidono caso particolare: cappio = ciclo di lunghezza 1
grafo aciclico = privo di cicli → se si ha bisogno che l'elemento precedente sia chiuso prima di passare al successivo, si deve verificare che non ci siano cicli che impediscono l'avvio.
grafo connesso = se si prende una qualsiasi coppia di vertici, esiste sempre un cammino che connette tale coppia (solo nei grafi non orientati).
componente connessa = è il sottografo massimale di un grafo per cui tutti i vertici sono mutualmente connessi (solo nei grafi non orientati).
Nei grafi orientati la raggiungibilità in un senso non implica la raggiungibilità nell'altro. grafo fortemente connesso = ogni coppia di vertici è raggiungibile in entrambi i sensi
grafo completo = esistono tutti gli archi per tutte le coppie di vertici:
* nei grafi non orientati: $\left|E\right|={\frac {\left(\left|V\right|-1\right)\cdot \left|V\right|}{2}}$
* nei grafi orientati: $\left|E\right|=\left(\left|V\right|-1\right)\cdot \left|V\right|$
dove:
* $\left|E\right|$ è il numero di archi;
* $\left|V\right|$ è il numero di vertici;
* $\left|V\right|-1$ è il numero di archi per ogni vertice.
$\left|E\right|$ può crescere al più con il quadrato di $\left|V\right|$:
* nei grafi densi: $\left|E\right|\cong \left|V^{2}\right|$
* nei grafi sparsi: $\left|E\right|\ll \left|V^{2}\right|$
grafo pesato: una funzione che riceve in input una coppia di nodi e restituisce il peso della coppia (generalmente un numero intero).

## Alberi

albero non radicato = grafo non orientato, connesso, aciclico (no nodi in particolare)
foresta = insieme di alberi

### Proprietà

G albero non radicato:
* ogni coppia di nodi è connessa da un solo cammino semplice;
* G connesso: rimuovere qualsiasi arco comporta sconnettere il grafo;
* $\left|E\right|=\left|V\right|-1$;
* G aciclico: aggiungere un arco comporta introdurre un ciclo.

### Alberi radicati

Si individua il nodo radice r → si stabiliscono delle relazioni padre-figlio tra le coppie di vertici (1 arco).
Se y ∈ cammino da r a x → y antenato, x discendente (più archi). L'antenato è proprio se x ≠ y.
Casi particolari:
* radice: no padre
* foglie: no figli

#### Proprietà

* grado = numero massimo di figli;
* profondità x = lunghezza del cammino da r (livello);
* altezza h = profondità massima.

#### Alberi binari

albero binario = albero con grado 2 (ogni nodo può avere 0, 1 o 2 figli). Definizione risorsiva:
* insieme di nodi vuoto (foglia)
* radice, sottoalbero sinistro, sottoalbero destro
albero binario completo = ogni nodo o è una foglia o ha 2 figli:
* numero di foglie: $2^{h}$
* numero di nodi: $\sum _{i=0}^{h}2^{i}=2^{h+1}-1$
albero binario bilanciato = tutti i cammini radice-foglia hanno uguale lunghezza (non c'è una foglia più vicina di altre alla radice). Un albero completo è sempre bilanciato (ma non viceversa).
albero binario quasi bilanciato = c'è al massimo uno scarto di una unità di lunghezza

## Note

* ↑ massimale: è il più grande dei sottoinsiemi per cui vale questa proprietà, cioè quello che comprende più vertici connessi possibile.
* ↑ Si ricorda la serie geometrica: $\sum _{i=0}^{h}x^{i}={x^{h+1}-1 \over x-1}$