Algoritmi e programmazione/Grafi e alberi

Da WikiAppunti.
Jump to navigation Jump to search
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.
/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]]/Grafi e alberi}}  [[{{#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 e alberi}}

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

  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: <math>\sum_{i=0}^h x^i = {x ^ {h+1} - 1 \over x - 1}</math>
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 4. Grafi e alberi.
/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]]/Grafi e alberi}}  [[{{#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 e alberi}}