PARTE QUINTA: Grafi

11/11/03:

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.

 

12/11/02:

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

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

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

Dispense: 77, 78, 79, 80, 81. 82. 83. 84. 85.

 

13/11/03:

Approfondimento: Correzione prova intermedia.