Clebsch graph
teoria dei grafi

6 crediti (48 ore), laurea magistrale in Informatica

DOCENTI: Nicolò Cesa-Bianchi

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, 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.

Programma

  1. Risultati di base
  2. Accoppiamenti e teorema max-flow min-cut
  3. Colorature, cricche, insiemi indipendenti e insiemi dominanti
  4. Grafi casuali ed il metodo probabilistico
  5. Analisi spettrale
  6. Cammini casuali su grafi

Dispense

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

  1. Basics (versione dell'8 Luglio 2020)
  2. Matchings and the max-flow min-cut theorem (versione dell'11 Aprile 2020)
  3. Colorings, cliques, independent and dominating sets (versione del 12 Aprile 2020)
  4. Random graphs and the probabilistic method (versione del 17 giugno 2020)
  5. Linear algebra background (versione del 3 Giugno 2020)
  6. Spectral clustering (versione del 13 Luglio 2020)
  7. Finding a planted clique (versione del 5 Giugno 2020)
  8. Random walks on graphs (versione dell'8 Giugno 2020)
  9. Slides su ranking spettrale e geometrico (seminario di Sebastiano Vigna)
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.

Fino al 31 dicembre 2020, l'esame verterà su un percorso scelto dallo studente fra questi quattro:

  1. Basics + Matchings + Colorings
  2. Basics + Random Graphs + Colorings
  3. Linear Algebra + Spectral Clustering + Planted clique
  4. Linear Algebra + Random Walks + Planted clique
Il ranking spettrale e geometrico è opzionale per tutti i percorsi.

Calendario lezioni

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