Corso di
Teoria dei Grafi e Reti di Flusso
(Ricerca Operativa - prima parte)
Prof. Stefano Giordani
Programma
a.a. 2021/2022
Obiettivi
del corso:
Introdurre aspetti
metodologici, teorici ed applicativi della teoria dei grafi e delle reti di
flusso. In questo contesto il corso si articola nei temi
fondamentali della modellazione di problemi di ottimizzazione su rete e dei metodi di
soluzione tramite algoritmi esatti e/o approssimati.
Programma:
Generalitą sui problemi di ottimizzazione e introduzione alla Ricerca Operativa
([0b] pag. 1-22). Grafi, introduzione e definizioni di base ([0a] pag. 29-65;
[2] pag. 1-4; [3] pag. 1-3; [4] pag. 1-9; [5] pag. 1-3). Cenni ed applicazioni
sull'analisi combinatoria: permutazioni, combinazioni, coefficienti binomiali e
proprietą ([4] pag. 240-246; [5] pag. 485-489). Grafi: introduzione e
definizioni di base. Sottografi, ordine e dimensione di un grafo. ([0a] pag.
29-65; [2] pag. 1-14; [3] pag. 1-15; [5] pag.1-11). Vicinati e grado di un nodo,
k-regolaritą di un grafo, fattorizzazioni ([0a] pag. 29-65; [2] pag. 1-14; [3]
pag. 1-15; [5] pag.1-11). Cammini su grafo, walk, trail, path e cicli ([0a] pag.
35-36, 61-63; [2] pag. 1-5; [3] pag.1-15; [5] pag. 1-11). Grafi e modelli: grafi
complemento, clique, insiemi indipendenti, insiemi ricoprenti, numero cromatico
di un grafo, definizione di grafo bipartito ([0a] 19-23, 50-57; [2] pag. 1-5;
[3] pag. 1-15; [5] pag. 1-11). Algoritmi: proprietą, algoritmi di ricerca
lineare e ricerca binaria ([4] pag. 92-103). Crescita di funzioni, notazione
Big-O ([4] pag. 74- 82). Complessitą degli algoritmi ([4] pag. 92-103).
Strutture dati per grafi: matrice di incidenza, matrice di adiacenza e lista di
adiacenza ([1] pag. 31-38; [5] pag. 1-11). Isomorfismo tra grafi. Componenti
connesse ([0a] pag. 389-425; [2] pag. 1-14; [3] pag. 1-15; [5] pag.1-15). Lemmi
e teoremi su grafi connessi ed aciclici ([0a] pag. 29-65; [3] pag. 5-8). Alberi
([0a] pag. 29-65; [2] pag. 1-14; [3] pag. 1-15; [5] pag.1-11). Grafi bipartiti
([0a] pag. 29-65; [2] pag. 1-14; [3] pag. 1-15; [5] pag.1-11). Cammini Euleriani
e teorema di Eulero ([0a] pag. 53-57; [2] pag. 1-14; [3] pag. 1-15). Cicli
Hamiltoniani ([0a] pag. 55-57; [4] pag. 583-586). Grafi planari: definizioni e
proprietą, grafi duali, teorema di Eulero ([5] pag. 233-243). Algoritmi di
ricerca su grafo: ricerca in ampiezza e ricerca in profonditą ([0a] 66-73; [1]
pag. 73-79). Ordinamenti topologici su grafo: algoritmo di ordinamento
topologico su grafo ([1] pag. 73-79). Problema del minimo albero ricoprente:
introduzione, teoremi di ottimalitą sui tagli e sui path ([0a] 321-337; [1] pag.
516-524). Algoritmo di Kruskal, algoritmo di Prim ([0a] 321-337; [1] pag.
516-524). Problemi di flusso su rete: generalitą. Problema dell'abbinamento,
Problema dell'assegnamento, Problema di trasporto; ([0a] pag. 3-18; [1] pag.
4-7, 469-471). Problema di ricerca di cammini minimi su grafo ([0a] pag.
157-210; [1] pag. 4-7, 93-95). Algoritmo di Dijkstra ([0a] pag. 173-177; [1] pag.
106-112). Algoritmo di Bellman-Ford ([0a] pag. 181-184; [1] pag. 133-144).
Algoritmo di Floyd-Warshall ([0a] pag. 204-210; [1] pag. 147-149). Problema di
flusso massimo su rete: reti residue, tagli e flusso ([0a] pag. 217-251; [1] pag.
166-169, 177- 187). Problema di flusso massimo su rete: algoritmo di Ford e
Fulkerson, teorema del massimo flusso e minimo taglio ([0a] pag. 221-244; [1]
pag. 4-7, 166-169, 177-187, 191-193). Implicazioni di natura combinatoria:
Algoritmo alternante aumentante per il problema dell'abbinamento su grafo
bipartito, Teorema di Konig, Teorema di Hall ([0a] pag. 257-262).
Pre-requisiti:
Analisi Matematica I,
Geometria, Fondamenti di Informatica.
Materiale
ufficiale del corso:
[0a] M.Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli.
Ottimizzazione su Rete: Modelli e Algoritmi. Isedi - De Agostini Scuola Spa, 2019.
[0b] M.Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli.
Ricerca Operativa: Programmazione Lineare, Intera e Non Lineare. Isedi - De Agostini Scuola Spa, 2018.
oppure:
[0c] M.Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli.
Ricerca Operativa. Isedi - De Agostini Scuola Spa, 2014.
Dispense aggiuntive e altro materiale forniti dal docente.
Altri testi
di consultazione
consigliati:
[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows. Prentice Hill, 1993.
[2] B. Bollobas. Modern Graph Theory. Springer Verlag, 1998.
[3] D. Jungnickel. Graphs, Network and Algorithms (3rd ed.). Springer, 2010.
[4] K.H. Rosen, Discrete Mathematics and its Applications (7-th ed.). McGraw-Hill International Edition, 2011.
[5] D.B. West. Introduction to Graph Theory. Prentice Hall, 2001.
Home | Didattica
| TGRF
Last modified on
01/09/2021
by Stefano
Giordani, stefano.giordani@uniroma2.it