Esercitazioni del 30/10 e 4/11/2008 (Tenute da Jacopo Avati)

Implementazione in C degli algoritmi per connettivita', connettivita' forte e calcolo componenti connesse (vedere slides). Elenco esercizi svolti:

* Dato un grafo orientato con pesi strettamente positivi, si costruisce un nuovo grafo che ha gli stessi nodi ma come archi solo quegli (u,v) che, fissato un nodo s, rispettano la legge d(s,u)+w(u,v)=d(s,v) (dove d(i,j) e' la distanza di peso minimo da i a j). Si dimostri che il secondo grafo e' aciclico.

* Dato un grafo non orientato con pesi tutti diversi, dimostrare che il secondo mst non e' unico.

* esercizio 2 dell'appello del 10/06/2008.

* esercizio 2 dell'appello del 1/2/2007.

* esercizio 3 dell'appello del 1/2/2007.