Esercitazioni 2020:

Materiali

Didattica a Distanza ai tempi della pandemia 2020:
- Esercitazione 2: BFS, DFS e topological sort: slides Lezione 17/4.
- Esercitazione 3: BFS, DFS, topological sort e SCC: slides Lezione 24/4 e animazione esecuzione di Tarjan.
- Esercitazione 4: Cammini minimi da sorgente unica: Dijkstra e Bellman-Ford. Proprietà degli MST: slides lezione 8/5.
- Esercitazione 5: Cammini minimi tra tutte le coppie. Altri esercizi su MST, Dijkstra e Bellman-Ford slides lezione 15/5.
- Esercitazione 6: Reti di Flusso. Altri esercizi su MST, Dijkstra e Bellman-Ford slides lezione 22/5.
- Esercitazione 7: Il problema dell'accoppiamento su grafi bipartiti. Esercizi su Reti di Flusso, MST, BFS, chiusura transitiva slides lezione 29/5.

Venerdì 24 febbraio 2020: Esercitazione 1 (aula III Castelnuovo)

Dimostrazioni
- Dato un grafo non orientato G, almeno uno tra G e il suo complementare è connesso.
- Dato un grafo non orietnato G = (V, E), esistono sempre almeno due nodi in V con lo stesso grado.
Rappresentazioni: complessità di alcuni semplici problemi su grafi diretti con matrici e liste di adiacenza.
- grado entrante/uscente; [ Cormen, 22.1-1 ]
- grafo trasposto [ Cormen, 22.1-3 ]
- grafo quadrato [ Cormen, 22.1-5 ]
Perle: problema del pozzo universale (grafo diretto rappresentato con matrice di adiacenza) [ Cormen, 22.1-6 ].
Alberi e vettori di padri: calcolare la distanza tra due nodi [e problemi collegati: minimo antenato comune e distanza dalla radice].

Esercizi per casa: in un albero rappresentato con vettori di padri, dato un nodo u calcolare l'insieme dei nodi del sottoalbero radicato in u.

Venerdì 17 aprile 2020: Esercitazione 2 (a distanza)

Capire la BFS
- In una BFS, gli alberi di visita dipendono dall'ordine delle liste di adiacenza, ma non le distanze dalla radice [ Cormen, 22.2-5 ].
- Alberi di cammini minimi potrebbero non essere il risultato di nessuna BFS [ Cormen, 22.2-6 ].
- Usare la BFS per determinare i nodi equidistanti da due nodi.
- Distanza tra due sottoinsiemi di nodi.
- Data la BFS di un grafo come vettore di padri, determinare se eliminare un arco modifica le distanze.
Capire la DFS
- verificare se alcuni alberi possono essere la visita DFS di un grafo (orientato o meno).
- fenomeni apparentemente contro-intuitivi nei tempi di entrata e di completamento in una DFS [ Cormen, 22.3-8, 22.3-9, 22.3-11 ]
- In un grafo non orientato, trovare un cammino che attraversa tutti gli archi 1 volta in entrambe le direzioni.
Topological Sort e Componenti Fortemente Connesse
- Orientare gli archi di un grafo indiretto per ottenere un DAG.
- Determinare se un nodo è principale. Trovare un nodo principale. Trovare l'insieme minimo di nodi principali.
Dimostrazioni
- BFS(G)=DFS(G) sse G è un albero.

Venerdì 24 aprile 2020: Esercitazione 3 (a distanza)

BFS & DFS
- Diametro di un albero: soluzione con doppia BFS [ Cormen, 22.2-8 ] e con DFS che calcola simultaneamente diametro e profondità.
- cammini minimi di archi rossi in grafo con archi rossi e neri [ Monti ].
Topological Sort
- Contare gli ordinamenti topologici in un DAG [ Monti ].
- Eliminare il numero minimo di archi per ottenere un DAG [ Monti ].
- Contare i cammini da u a v in un DAG [ Cormen, 22.4-2 ]: versione efficiente con Programmazione Dinamica.
- Algoritmo alternativo per Topological Sort [ Cormen, 22.4-5 ]: strutture dati per renderlo efficiente.
Componenti Fortemente Connesse
- Esempio di esecuzione dell'algoritmo di Tarjan.
- Come cambia il numero di SCC aggiungendo un arco [ Cormen, 22.5-1 ].
- Dato G, trovare un grafo G' con le stesse SCC, ma un numero minimo di archi [ Cormen, 22.5-6 ].
- Classificare archi interni/esterni alle SCC [ Monti ].
Esercizi aperti (discussi ma non risolti)
- Determinare se un grafo diretto è semi-connesso [ Cormen, 22.5-7 ].
- Determinare se un grafo diretto è singolarmente connesso [ Cormen, 22.3-13 ].
- Alcuni problemi su grafi s-t connessi: trovare il ciclo più vicino alla sorgente s, determinare cammini disgiunti [ Salvo ].
- Altri problemi: determinare distanza media, nodi a distanza massima, grafo parzialmente orientato.

Venerdì 8 maggio 2020: Esercitazione 4 (a distanza)

Afffinità e divergenze: Dijkstra vs MST
- Dijkstra e pesi negativi. Aggiungere costanti additivi nei cammini minimi e negli MST [ Monti ].
- Alberi minimi e DAG di cammini minimi [ Monti ]. Problemi sull'unicità dell'MST [ Monti e Cormen, 23.1-6 ]
Algoritmo di Dijkstra
- Verifica di una soluzione di cammini minimi in O(n+m) [ Cormen, 24.4-4 ].
- Contare i cammini minimi [ Monti ].
- Cammino super-minimo [ Monti ].
Proprietà degli MST
- Controesempio al converso del Teorema dell'arco leggero [ Cormen, 23.1-2 ].
- Proprietà degli archi leggeri [ Cormen, 23.1-3 ] e [ Cormen, 23.1-4 ]. Sottoinsiemi di archi di peso minimo [ Cormen, 23.1-7 ]
- Archi pesanti [ Cormen, 23.1-5 ].
Algoritmo di Bellman-Ford
- Terminazione di Bellman-Ford in un numero di iterazioni pari al cammino minimo di lunghezza massima [ Cormen, 24.2-3 ]
- Marcare i nodi raggiungibili dalla sorgente attraverso un ciclo negativo [ Cormen, 24.2-4 ].
- Elencare i vertici appartenenti a un ciclo di peso negativo [ Cormen, 24.2-6 ].

Venerdì 15 maggio 2020: Esercitazione 5 (a distanza)

Cammini minimi tra tutte le coppie
- `Moltiplicazione' di matrici e generalizzazione di Bellman Ford: algoritmo naif. Ottimizazzione con Programmazione Dinamica [ Cormen, 25.2 ].
- Ricostruire la matrice dei padri dalla matrice dei costi [ Cormen, 25.2-6 ]
- Rilevare la presenza di un ciclo negativo [ Cormen, 25.2-9 ]
- Determinare la lunghezza minima di un ciclo negativo [ Cormen, 25.2-10 ]
- Floyd-Warshall e chiusura transitiva di un grafo diretto [ Cormen, 25.4 ]. Il caso dei cicli negativi [ Cormen, 25.3-6 ].
- Chiusura transitiva di un DAG in O(nm).
Cammini minimi da sorgente unica e MST
- Cammini minimi in un DAG [ Cormen, 24.3 ]
- Unicità della sequenza dei pesi degli archi in un MST [ Cormen, 23.1-9 ].
- Perché fallisce il Divide et Impera nel calcolo dell'MST [ Cormen, 23.3-8 ]
- Algoritmo di Kruskal con pesi limitati sugli archi [ Cormen, 23.3-4 ]

Venerdì 22 maggio 2020: Esercitazione 6 (a distanza)

Reti di Flusso
- Reti, flusso, tagli, rete residua, cammini aumentanti. Massimo flusso/taglio minimo.
- Algoritmi di Ford-Fulkerson ed Edmonds-Karp per il massimo flusso.
- Esercizi: two disjoint paths problem: varie versioni.
Cammini minimi da sorgente unica e MST
- Affidabilità di un canale di comunicazione [ Cormen, 24.4-6 ]
- Dijkstra con pesi interi limitati [ Cormen, 24.4-7, 24.4-8, 24.4-9 ]
- Algoritmo di Prim con pesi limitati sugli archi [ Cormen, 23.3-5 ]
- Algortimi alternativi per MST: corretti o meno? [ Cormen, 23.4 ]

Venerdì 29 maggio 2020: Esercitazione 7 (a distanza)

Reti di Flusso
- Accoppiamento su grafi bipartiti: uso di Ford-Fulkerson.
- Esercizi: basterebbero sempre E cammini aumentanti per trovare il flusso massimo [ Cormen, 26.2-10 ]
- Arco-connettività con Reti di flusso [ Cormen, 26.2-11 ]
- Taglio super-minimo [ Cormen, 26.2-13 ]
- Massimo flusso dopo aver modificato la capacità di un arco [ Cormen, 26.4 ]
Potpourri finale
- MST dopo aver diminuito il peso di un arco [ Cormen, 23.1-11 ]
- Distanze minime su grafo che rovescia archi al tempo T [ Monti, esonero 2019 ]
- Ridurre il problema della chiusura transitiva alla chiusura transitiva di un DAG [ Cormen, 25.3-9 ]