- Docente: Aristide Mingozzi
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Cesena
- Corso: Laurea in Scienze dell'informazione (cod. 0101)
Conoscenze e abilità da conseguire
Obiettivo principale del corso è di presentare gli elementi essenziali
della teoria dei grafi, con particolare attenzione alle applicazioni,
gli aspetti algoritmici, la loro implementazione e complessità
computazionale.
Contenuti
Introduzione:
Concetti base e notazione
Cammini e cicli
Connettività
Grafi bipartiti
Alberi ed Arborescenze:
Proprietà degli alberi
Alberi di costo minimo
Arborescenze di costo minimo
Flussi:
Esempi di problemi riconducibili a flussi in un grafo
Flusso massimo in un grafo
Algoritmi
Flussi a costo minimo
Algoritmi
Matching:
Grafi bipartiti
Grafi generali
Algoritmi
Grafi Euleriani:
Circuiti Euleriani
Il problema del postino cinese
Algoritmi
Grafi Planari:
Formula di Eulero
Caratterizzazione dei grafi planari
Teorema di Kuratowski
Dualità
Risoluzione di Problemi Reali su Grafi
Metodi esatti ed euristici per:
- Vertex routing
- Arc routing
- Crew scheduling
- Project scheduling
- Lot sizing
Testi/Bibliografia
R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
M. Gondran, M. Minoux, Graphs and Algorithms, John Wiley.
Colin R. Reeves, Modern heuristic techniques for combinatorial problems, Blackwell, Oxford.
Metodi didattici
Durante le lezioni verranno presentati sia gli aspetti teorici che
pratici relativi ai diversi argomenti trattati. Esempi, esercizi ed
esercitazioni di laboratorio aiuteranno lo studente a comprendere l'uso
degli strumenti matematici presentati.
Modalità di verifica e valutazione dell'apprendimento
Progetto e prova scritta e orale.
Strumenti a supporto della didattica
Dispense, videoproiettore, PC, lavagna luminosa e laboratori.
Orario di ricevimento
Consulta il sito web di Aristide Mingozzi