Introduzione alla teoria dei grafi. Il problema dei ponti di Koenigsberg.
Definizioni e proprietà elementari dei grafi. Grafi completi. Matrici associate a un grafo: matrice di adiacenza e matrice di incidenza. Il primo teorema della teoria dei grafi.
Isomorfismi e automorfismi dei grafi.
Operazioni elementari sui grafi: unione, intersezione, differenza, etc. Sottografi, sottografi indotti e sottografi generanti.
Il grado dei vertici. Il grado minimo, il grado medio e il grado massimo di un grafo. Grafi regolari. Il teorema di König.
Cammini e cicli in un grafo: definizioni e principali risultati. Passeggiate e percorsi in un grafo. Calcolo del numero di passeggiate tra due vertici attraverso la matrice di adiacenza.
Grafi connessi. Le componenti di un grafo. Grafi k-connessi e grafi l-lato-connessi. Il teorema di Mader (senza dimostrazione).
Alberi e foreste. Caratterizzazione degli alberi. Alberi radicati. Alberi radicati normali e alberi normali generanti (depth-first search trees). Ogni grafo connesso contiene un albero normale generante.
Grafi bipartiti e grafi r-partiti.
Contrazioni e minori. Suddivisioni e minori topologici.
Cammini Euleriani. Il teorema di Eulero.
Altre nozioni di grafo: ipergrafi, grafi diretti (digrafi), grafi orientati, multigrafi.
Grafi planari. Alcuni richiami di topologia. Grafi massimamente piani e triangolazioni piane. La formula di Eulero. Grafi planari e poliedri. I cinque poliedri regolari. Caratterizzazione dei grafi planari. Il teorema di Kuratowski.
Colorazioni di grafi. Colorazioni dei vertici e colorazioni dei lati di un grafo. Il numero cromatico e l'indice cromatico. Colorazioni dei grafi planari: il teorema dei quattro colori (senza dim.), il teorema dei cinque colori (con dim.). Relazioni tra il numero cromatico e altri invarianti di un grafo. Algoritmi per la colorazione dei vertici
Altro:
L'esame consiste in una prova orale. Oltre alla modalità classica (domande sul programma svolto durante il corso), lo studente può scegliere di preparare una lezione, della durata di 45 minuti circa, su un particolare argomento, da concordare con il docente. Per la scelta degli argomenti e per fissare la data dell'esame, si prega di contattare il docente personalmente, oppure per posta elettronica.
