Algoritmi/Grafi e alberi

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