Teoria dei grafi

A.A. 2021/2022
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
In relazione alle modalità di erogazione delle attività formative per l'a.a. 2021-22, verranno date indicazioni più specifiche nei prossimi mesi, in base all'evoluzione della situazione sanitaria.
Programma
L'obiettivo del corso è fornire un'introduzione alla teoria dei grafi con particolare enfasi rivolta agli aspetti algoritmici e probabilistici.

Risultati di base
Colorature, cricche, insiemi indipendenti e insiemi dominanti
Grafi casuali ed il metodo probabilistico
Analisi spettrale di grafi
Cammini casuali su grafi
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 presso ncesa-bianchitg.ariel.ctu.unimi.it/

Testo di riferimento: 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
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007