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.

Diario

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 ]

-- Ivano Salvo - 2020-04-18

-->