Algoritmi e programmazione/Grafi e alberi

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Grafi e alberi}}/Gli algoritmi di ordinamento{{#ifcategory:Traduzioni\|/Grafi e alberi\|\|/Grafi e alberi}}\|3. Gli algoritmi di ordinamento]]	[[{{#ifcategory:Traduzioni\|/Grafi e alberi\|Algoritmi e programmazione\|/Grafi e alberi}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Grafi e alberi}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/Grafi e alberi}}/La ricorsione{{#ifcategory:Traduzioni\|/Grafi e alberi\|\|/Grafi e alberi}}\|5. La ricorsione]]

Grafi[modifica | modifica sorgente]

2 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

3-4 cappio = arco che ritorna sul vertice di partenza (solo nei grafi orientati)

5 Due vertici si dicono tra loro adiacenti se sono connessi da un arco.

6 grado di un vertice = numero di archi che insistono su quel vertice
per i grafi orientati: in_degree (entranti), out_degree (uscenti)

7 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.

9 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.

10 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^[1] di un grafo per cui tutti i vertici sono mutualmente connessi (solo nei grafi non orientati).

11 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

14 grafo completo = esistono tutti gli archi per tutte le coppie di vertici:

nei grafi non orientati: <math>\left| E \right| = \frac{\left(\left|V\right| - 1\right) \cdot \left| V \right|}{2}</math>
nei grafi orientati: <math>\left| E \right| = \left(\left|V\right| - 1\right) \cdot \left| V \right|</math>

dove:

<math>\left|E\right|</math> è il numero di archi;
<math>\left|V\right|</math> è il numero di vertici;
<math>\left|V\right| - 1</math> è il numero di archi per ogni vertice.

13 <math>\left|E\right|</math> può crescere al più con il quadrato di <math>\left|V\right|</math>:

nei grafi densi: <math>\left|E\right| \cong \left| V^2 \right|</math>
nei grafi sparsi: <math>\left|E\right| \ll \left| V^2 \right|</math>

15 grafo pesato: una funzione che riceve in input una coppia di nodi e restituisce il peso della coppia (generalmente un numero intero).

Alberi[modifica | modifica sorgente]

25 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;
<math>\left|E\right| = \left|V\right| - 1</math>;
G aciclico: aggiungere un arco comporta introdurre un ciclo.

Alberi radicati[modifica | modifica sorgente]

27 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

29 Proprietà

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

Alberi binari[modifica | modifica sorgente]

30 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

31 albero binario completo = ogni nodo o è una foglia o ha 2 figli:

numero di foglie: <math>2^h</math>
numero di nodi: <math>\sum_{i=0}^h 2^i = 2 ^ {h+1} - 1</math>^[2]

32 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).

33 albero binario quasi bilanciato = c'è al massimo uno scarto di una unità di lunghezza

Note[modifica | modifica sorgente]

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