====== Grafi ======

Nella prima parte della lezione del 10/12, abbiamo introdotto il concetto di [[wp>Graph_(mathematics)|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 [[wp>Minimum_spanning_tree|minimum spanning tree]] di un grafo:
  * [[wp>Dijkstra's_algorithm|Algoritmo di Dijkstra]] e [[wp>Prim's_algorithm
|Prim-Jernik-Dijkstra]]
  * [[wp>Floyd–Warshall_algorithm|Algoritmo di Floyd]]
  * [[wp>Kruskal's_algorithm|Algoritmo di Kruskal]]
  * [[wp>Depth-first_search|Visita depth-first]]
  * [[wp>Breadth-first_search|Visita breadth-first]]
  * [[wp>Topological_sorting|Ordinamento topologico]] (solo per grafi diretti aciclici)