Lezione del 27/11/2008

Esercizio: Un albero dei cammini minimi di un grafo e' ancora un albero dei cammini minimi dello stesso grafo nel caso in cui a tutti gli archi viene sommata la stessa costante? Cammini minimi tra tutte le coppie di nodi di un grafo orientato con cicli di costo non negativo: cammini minimi k-vincolati; algoritmo di Floyd-Warshall per il calcolo di tutte le distanze minime e cammini minimi.

Lezione del 25/11/2008

Cammini minimi su grafi con pesi non negativi: Condizione di Dijkstra sulla appartenenza di un arco (u,v) al cammino minimo da s a v; Algoritmo di Dijkstra ed implementazione con heap, correttezza e complessita' computazionale O(|E|log |V|). Esercizio: Un MST di un grafo e' ancora un MST nel caso in cui a tutti gli archi viene sommata la stessa costante? Ed nel caso di un albero dei cammini minimi?

Avviso

Nella sezione "Materiale didattico" di questo blog e' stato pubblicato un documento contenente la raccolta degli esercizi svolti a lezione e relativa soluzione.

Lezione del 20/11/2008

Cammini minimi di grafi diretti pesati: condizione necessaria e sufficiente affinche' un arco faccia parte di un cammino minimo; algoritmo di Bellman-Ford per il calcolo dell'albero dei cammini minimi nel caso in cui il grafo non contenga cicli negativi; correttezza e complesita' computazionale dell'algoritmo di Bellman-Ford.

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.

Lezione del 18/11/2008

Esercizio: il minimo albero ricoprente ha il minimo arco di peso massimo tra tutti gli alberi coprenti. Cammini minimi in grafi diretti: definizioni, prime proprieta' per grafi senza cicli negativi; albero dei cammini minimi: definizione e dimostrazione di esistenza.

Lezione del 13/11/2008

Implementazione nel linguaggio C della struttura dati Union-Find (slides), dell'algoritmo di Kruskal (slides) e dell'algoritmo di Prim (slides). Esercizio: Un grafo non diretto, connesso con pesi sugli archi tutti diversi ammette un unico minimo albero coprente.

Lezione del 11/11/2008

Algoritmo di Prim per il calcolo del minimo albero coprente: Correttezza, Implementazione non efficiente; Implementazione efficiente dell'algoritmo con tempo di calcolo O(|E| log |V|) che utilizza la struttura dati Heap.

Lezione del 06/11/2008

Implementazione ingenua e non efficiente dell'algoritmo di Kruskal; Struttura dati Union-Find; Utilizzo della struttura dati Union-Find per una implementazione efficiente dell'algoritmo di Kruskal con tempo di calcolo O(|E| log |V|).