Algoritmi e programmazione/Grafi e alberi

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.
Gtk-go-back-ltr.svg  3. Gli algoritmi di ordinamento Gtk-home.svg  Algoritmi e programmazione 5. La ricorsione  Gtk-go-forward-ltr.svg

Grafi[modifica]

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

13 \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|

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]

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

Alberi radicati[modifica]

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 xy antenato, x discendente (più archi). L'antenato è proprio se xy.

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]

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: 2^h
  • numero di nodi: \sum_{i=0}^h 2^i = 2 ^ {h+1} - 1[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]

  1. massimale: è il più grande dei sottoinsiemi per cui vale questa proprietà, cioè quello che comprende più vertici connessi possibile.
  2. Si ricorda la serie geometrica: \sum_{i=0}^h x^i = {x ^ {h+1} - 1 \over x - 1}
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.
Gtk-go-back-ltr.svg  3. Gli algoritmi di ordinamento Gtk-home.svg  Algoritmi e programmazione 5. La ricorsione  Gtk-go-forward-ltr.svg