Lezione del 23/10/2008

Regola del taglio: Esiste un MST che contiene il minimo arco di un taglio del grafo di partenza; Tutti gli archi dell'MST sono archi di peso minimo di qualche taglio del grafo di partenza. Algoritmo di Kruskal per il calcolo dell'MST. Esercizio: i grafi a torneo contengono un cammino Hamiltoniano.