Alberi e cammini¶
Parte 2 del corso, volume 2 delle dispense: capitoli 2–3.
Alberi ricoprenti di costo minimo (Kruskal, Prim, proprietà del taglio e del ciclo) e cammini minimi (grafi aciclici, Bellman–Ford, Dijkstra), con i potenziali come certificato di ottimalità.
-
2. Alberi ricoprenti di costo minimo
Il problema dell'albero di copertura minimo · Tagli e cicli · La proprietà di taglio e la proprietà di ciclo · L'algoritmo greedy generico
-
3. Cammini minimi
Problemi del percorso più breve · Condizioni e potenziali di ottimalità · La formulazione della programmazione lineare · Percorsi più brevi nei grafici aciclici