Teoria dei grafi
A.A. 2021/2022
Learning objectives
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.
Expected learning outcomes
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.
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Course syllabus and organization
Edizione unica
Responsabile
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
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.
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.
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.
La valutazione, espressa in trentesimi, tiene conto del livello di padronanza degli argomenti, della chiarezza espositiva e della proprietà di linguaggio.
Educational website(s)
Professor(s)