Teoria dei grafi

A.A. 2019/2020
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
I grafi sono strutture matematiche fondamentali usate per modellare relazioni fra coppie di oggetti. Questo insegnamento descriverà alcuni dei concetti fondamentali della teoria dei grafi, fra cui i cicli, gli accoppiamenti, le colorature, la connettività e i grafi estremali. La seconda parte dell'insegnamento si occuperà di alcuni aspetti avanzati, come ad esempio i grafi casuali e la teoria spettrale dei grafi, che hanno recentemente avuto un impatto notevole sull'informatica.
Risultati apprendimento attesi
Al termine dell'insegnamento, gli studenti saranno in grado di: (1) dimostrare i principali teoremi strutturali della teoria dei grafi; (2) comprendere le proprietà fondamentali di alcuni modelli di grafi casuali; (3) descrivere le principali quantità spettrali misurabili sui grafi e definirne il loro utilizzo algoritmico. Questi obiettivi verranno misurati attraverso una discussione orale la cui valutazione determinerà il voto finale.
Programma e organizzazione didattica

Edizione unica

Periodo
Secondo semestre
Programma
L'obiettivo del corso è fornire un'introduzione alla teoria dei grafi con particolare enfasi rivolta agli aspetti algoritmici e probabilistici.

1. Concetti fondamentali
2. Risultati di base su alberi e cicli
3. Accoppiamenti
4. Connettività
5. Teoria estremale dei grafi
6. Grafi casuali
7. Teoria spettrale dei grafi
8. Clustering spettrale
9. Ranking spettrale e geometrico
Prerequisiti
Si richiedono nozioni di base di analisi matematica, algebra lineare e statistica.

E` fortemente consigliato il superamento degli esami seguenti: Matematica del continuo, Matematica del discreto, Statistica e analisi dei dati.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
Il riferimento principale sono le dispense disponibili tramite ncesa-bianchitg.ariel.ctu.unimi.it/

Un riferimento ulteriore è il libro di testo: Reinhard Diestel, "Graph Theory", Springer Verlag, 2017.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova orale, relativa agli argomenti trattati nell'insegnamento.
La valutazione, espressa in trentesimi, tiene conto del livello di padronanza degli argomenti, della chiarezza espositiva e della proprietà di linguaggio.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Siti didattici
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007