Teoria dei grafi
A.A. 2025/2026
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.
Periodo: Secondo quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Secondo quadrimestre
Programma
Nozioni di base: gradi e vicinati, nozioni di connettività, camminate e percorsi, percorsi euleriani e hamiltoniani.
Colorazioni e invarianti: numeri cromatici, clique, numero di clique, insiemi indipendenti, insiemi dominanti.
Grafi aleatori: grafi di Erdos-Renyi e loro numero di clique, e metodo probabilistico. Richiami di algebra lineare: autovettori, autovalori, teorema spettrale.
Clustering spettrale dei grafi: laplaciane, conduttanza, disuguaglianza di Cheeger, vettore di Fiedler.
Planted clique: definizione e algoritmi.
Camminate aleatorie su grafi: matrici di transizione, convergenza, distribuzione stazionaria, tempo di mixing.
Stochastic block models: teoria perturbativa e recupero dei blocchi.
Colorazioni e invarianti: numeri cromatici, clique, numero di clique, insiemi indipendenti, insiemi dominanti.
Grafi aleatori: grafi di Erdos-Renyi e loro numero di clique, e metodo probabilistico. Richiami di algebra lineare: autovettori, autovalori, teorema spettrale.
Clustering spettrale dei grafi: laplaciane, conduttanza, disuguaglianza di Cheeger, vettore di Fiedler.
Planted clique: definizione e algoritmi.
Camminate aleatorie su grafi: matrici di transizione, convergenza, distribuzione stazionaria, tempo di mixing.
Stochastic block models: teoria perturbativa e recupero dei blocchi.
Prerequisiti
Solida conoscenza delle nozioni base della matematica continua (analisi di funzione) e discreta (combinatorica) e dell'informatica teorica (algoritmi, complessità).
Metodi didattici
Lezioni frontali con l'aiuto di lavagna e diapositive.
Materiale di riferimento
· Reinhard Diestel, Graph Theory (5th edition), Springer, 2017.
· Dispense che verranno fornite dal docente.
· Dispense che verranno fornite dal docente.
Modalità di verifica dell’apprendimento e criteri di valutazione
Esame orale.
Docente/i