Grafi
Nella prima parte della lezione del 10/12, abbiamo introdotto il concetto di grafo, e alcuni concetti accessori:
- Vertice
- Lato/arco
- Cammino (semplice o meno)
- Ciclo (semplice o meno)
- Distanza fra vertici
- Cammino minimo fra due vertici
Abbiamo visto alcune fra le principali proprietà dei grafi, in particolare la disuguaglianza triangolare per le distanze in grafi i cui lati abbiano pesi non negativi.
Per finire, abbiamo trattato i principali algoritmi relativi al calcolo delle distanze e dei cammini minimi, e del minimum spanning tree di un grafo:
- Ordinamento topologico (solo per grafi diretti aciclici)
