Clebsch graph
teoria dei grafi

6 crediti (48 ore), laurea magistrale in Informatica

DOCENTI: Nicolò Cesa-Bianchi
Guest lecturers: Emmanuel Esposito e Marco Bressan

Avvisi

Obiettivi

I grafi sono strutture matematiche fondamentali usate per modellare relazioni fra coppie di oggetti. A seguito della diffusione delle reti digitali (per esempio le reti sociali, le reti di interazione fra utenti e prodotti, le reti ipertestuali, le reti biologiche, etc.) , i grafi sono diventati uno strumento chiave per l'analisi dei dati. Questo insegnamento descriverà alcuni dei concetti fondamentali della teoria dei grafi, fra cui i cicli, la connettività, le colorature, le cricche. La seconda parte dell'insegnamento si occuperà di alcuni aspetti avanzati, come ad esempio il clustering su grafi e i cammini casuali su grafi.

Programma preliminare

  1. Risultati di base
  2. Colorature, cricche, insiemi indipendenti e insiemi dominanti
  3. Grafi casuali ed il metodo probabilistico
  4. Analisi spettrale
  5. Cammini casuali su grafi
  6. Expanders

Dispense

Versioni preliminari in aggiornamento costante. Per favore segnalate eventuali errori.

  1. Basics (versione dell'11 Marzo 2024)
  2. Colorings, cliques, independent and dominating sets (versione del 12 Marzo 2024)
  3. Random graphs and the probabilistic method (versione del 27 Marzo 2024)
  4. Linear algebra background (versione del 5 Giugno 2022)
  5. Spectral clustering (versione del 13 Aprile 2022)
  6. Finding a planted clique (versione del 27 Aprile 2022)
  7. Random walks on graphs (versione dell'8 giugno 2022)
Materiale bibliografico

Esami

L'esame consiste in una prova orale che comprende anche le dimostrazioni spiegate a lezione. La data viene fissata su appuntamento e il voto verrà verbalizzato nel primo appello utile.

Calendario lezioni

Sfogliate le pagine del calendario e cliccate sulle date per trovare i riassunti e le date delle prossime lezioni.