Esercitazione del 27/01/2009 - ULTIMA LEZIONE

Minimo Steiner Tree di un grafo: caso particolare in cui i nodi da coprire sono 3. NP-completezza di Max NAE 3-Sat via riduzione da Max 2-Sat.

Esercitazione del 22/01/2009

Eccentricita' dei nodi di un grafo, calcolo dei centri: diverse soluzioni. NP-completezza di Max Exacly 2-Sat via riduzione da Max 2-Sat.

Esercitazione del 15/01/2009

Ciclo di costo minimo passante per un arco di un grafo fortemente connesso con pesi positivi. NP-Completezza di Max 2-Sat: riduzione da 3-Sat.

Esercitazione del 13/01/2009

Ripasso generale sull'NP-completezza. NP-completezza del problema dell'Hitting Set.

Esercitazione del 08/01/2009 (Tenuta da Jacopo Avati)

Elenco degli esercizi svolti:

* Esercizio 1 dell'appello del 18/09/2007;

* Esercizio 1 dell'appello del 05/07/2007;

* Dato un grafo G pesato, non orientato e connesso ed un nodo r, dire se esiste una costante che limita superiormente il rapporto tra il costo dell'albero dei cammini minimi di G con radice r ed il costo di un minimo albero coprente di G;

* Dato un grafo non orientato, connesso e con pesi sugli archi positivi e tutti distinti e dato un nodo r, si dica se il minimo albero coprente e l'albero dei cammini minimi da r hanno sempre archi in comune.

* Esercizio 1 dell'appello del 10/06/2008;

Lezione del 09/12/2008

Riduzioni polinomiali e risultati negativi: Il problema del minimo insieme convesso non puo' essere risolto in tempo o(n log n). Esercizio: Un algoritmo di complessita' temporale lineare per il calcolo dell'albero dei cammini minimi quando i pesi degli archi sono interi e di numero costante.

Lezione del 02/12/2008

Implementazione in C degli algoritmi per il calcolo dei cammini minimi: Bellman-Ford; Dijkstra; Floyd-Warshall (vedere slides). Esercizio: proprieta' dell'insieme di archi costituito dall'unione dei minimi archi incidente ai nodi del grafo nel caso in cui tutti gli archi hanno peso diverso.

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?

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 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.