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.