Teoria dei grafi

A.A. 2019/2020
Insegnamento per
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Al termine del corso, 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 definirà il voto finale.

Struttura insegnamento e programma

Edizione attiva
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Programma
1. Concetti fondamentali
2. Risultati di base su alberi e cicli
3. Accoppiamenti
4. Connettività
5. Grafi planari
6. Teoria dei grafi estremi
7. Grafi casuali
8. Teoria spettrale dei grafi
9. Clustering di grafi
Prerequisiti e modalità di esame
Prerequisiti: matematica del discreto, matematica del continuo, algebra lineare, probabilità e statistica.

L'esame consiste in una prova orale.
Metodi didattici
Lezioni frontali
Materiale didattico e bibliografia
Reinhard Diestel, "Graph Theory", terza edizione (o successiva), Springer Verlag.

Dispense del docente.
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007