PARTE QUINTA: Grafi

9/11/04:
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.

 
10/11/04:
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: Esercizi di visita di un grafo.
Dispense: 77, 78, 79, 80, 81. 82. 83. 84. 85.