PARTE QUINTA: Grafi

12/11/02:

Introduzione: cammino Euleriano, grafi orientati e non, grado di un vertice, adiacenza tra vertici e tra archi, cammino, ciclo, connessione,

sottografo, sottografo indotto, grafo completo, grafo pesato. Rappresentazione di un grafo in memoria: liste di adiacenza e relativi vantaggi e svantaggi.

Rappresentazione di un grafo in memoria tramite matrice di adiacenza e relativi vantaggi e svantaggi.

Approfondimento: Algoritmo per la verifica della completezza di un grafo, per il calcolo del grado e per la trasformazione da

rappresentazione tramite matrice di adiacenza a liste di adiacenza.

Dispense: 69, 70, 71, 72, 73, 74, 75, 76.

 

13/11/02:

Visita in ampiezza di un grafo: schema di visita, algoritmo e complessità, esempi.

Approfondimento: Algoritmo per la costruzione della chiusura transitiva di un grafo rispetto ad uno specifico nodo sorgente.

Dispense: 77, 78, 79, 80, 81.

 

14/11/02:

Visita in profondità di un grafo: schema di visita, algoritmo e complessità, esempi. Proprietà di un albero DFS.

Approfondimento: Correzione prova intermedia.

Dispense: 82, 83, 84, 85.