Algoritmi/Grafi e alberi

Indice del libro

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[1] 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:  
  • nei grafi orientati:  

dove:

  •   è il numero di archi;
  •   è il numero di vertici;
  •   è il numero di archi per ogni vertice.

  può crescere al più con il quadrato di  :

  • nei grafi densi:  
  • nei grafi sparsi:  

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

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;
  •  ;
  • G aciclico: aggiungere un arco comporta introdurre un ciclo.

Alberi radicati

modifica

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
Proprietà
  • grado = numero massimo di figli;
  • profondità x = lunghezza del cammino da r (livello);
  • altezza h = profondità massima.

Alberi binari

modifica

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:  
  • numero di nodi:  [2]

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

  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: