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. 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 i grafi casuali e la teoria spettrale dei grafi, che hanno recentemente avuto un impatto notevole sull'informatica.

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. Teoria dei minori

Dispense

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

  1. Basics (versione dell'8 Marzo 2022)
  2. Colorings, cliques, independent and dominating sets (versione del 20 Marzo 2022)
  3. Random graphs and the probabilistic method (versione del 27 Marzo 2022)
  4. Linear algebra background (versione del 5 Giugno 2022, aggiunto Teorema di Courant-Fischer)
  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)
  8. Graph Minors 1 (versione del 23 Maggio 2022)
  9. Graph Minors 2 (versione del 25 Maggio 2022)
  10. Graph Minors 3 (versione del 30 Maggio 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.