Avviso

La lezione di oggi, 30 ottobre, non si e' tenuta poiche' il Consiglio di Facoltà ha disposto una giornata di blocco della didattica per consentire agli studenti che lo vogliano di partecipare alla manifestazione nazionale contro la legge 133.

Errata corrige

E' stato risolto il problema sulla versione 20081014 di libgraphs, non conteneva il Makefile.

Avviso

Contrariamente a quanto affermato in un precedente post, le lezioni del 28, 30 ottobre e 4 novembre si svolgeranno regolarmente. Saranno tenute dal Dott. Jacopo Avati che svolgera' alcuni temi di esame.

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.

Avviso

Le lezioni del 28 e 30 ottobre e del 4 novembre non si terranno. Queste verranno recuperate gia' a partire da domani (23 ottobre) in quanto la lezione terminera' alle 14:00 anziche' alle 13:00.

Lezione del 21/10/2008

Grafi diretti: algoritmo di visita generica; arborescenza coprente; grafi fortemente connessi; algoritmo per la verifica della forte connettivita' di un grafo fortemente connesso in tempo O(|V| + |E|). Minimo albero coprente (MST) di un grafo non diretto e pesato sugli archi; Regola del ciclo (l'arco di peso massimo di un ciclo non appartiene a nessun MST ed ogni arco non nel MST crea un ciclo nell'MST composto di archi di peso minore).

Lezione del 16/10/2008

Complessita' della visita di un grafo rappresentato mediante liste di adiacenza; Implementazione delle strutture di appoggio per la visita di grafi (pile/code); Proprieta' dell'albero risultante dalla visita in ampiezza (il livello di un nodo sull'albero corrisponde alla distanza sul grafo del nodo dalla sorgente della visita); Visita di grafi ed esistenza di cicli.

Lezione del 14/10/2008

Albero di visita di un grafo; Realizzazione dell'algoritmo generico di visita con Pila e Coda (con implementazione dettagliata in C, vedere slides ed il file visit.c per un esempio di applicazione); Visita in ampiezza; Esempio: calcolo del diametro di un grafo.

Lezione del 9/10/2008

Componenti connesse di un grafo diretto; Partizione in componenti connesse, unicita' della partizione; Ricerca della componente connessa contenente un nodo dato, algoritmo di visita generica di un grafo e sua correttezza.

Lezione del 7/10/2008

Grafi, cenni preliminari: grafi diretti, non diretti, vicinato e grado di un nodo, cammini, cicli. Operatori basilari su grafi: creazione di un grafo; verifica dell'esistenza di un arco; inserimento di un nuovo arco; cancellazione di un arco; inserimento di un nuovo nodo; cancellazione di un nodo. Rappresentazioni dei grafi (e degli operatori) col calcolatore: Liste di archi; Matrice di adiacenza; Vettore di liste di adiacenza (con implementazione dettagliata in C, vedere slides). Valutazione delle tre rappresentazioni dal punto di vista della complessita' computazionale.

Per un esempio di utilizzo delle primitive su grafi definite a lezione si veda il programma simple.c nella cartella examples della libreria per la gestione dei grafi libgraphs.zip. Per le istruzioni di compilazione si faccia riferimento al file readme.txt che si trova all'interno dell'archivio.