Dispense di teoria dei grafi e combinatoria del Prof. C. Casolo, a.a. 2016-17, reperibili al seguente indirizzo
http://web.math.unifi.it/users/casolo/
Obiettivi Formativi
Acquisire i fondamenti di teoria dei grafi e loro applicazioni.
Prerequisiti
Nessuno
Metodi Didattici
Lezioni frontali e seminari.
Modalità di verifica apprendimento
Esame orale. Alla valutazione finale concorre l'eventuale partecipazione degli studenti alla attività seminariale.
Programma del corso
Il presente programma fa riferimento alle note del corso.
[Capitolo 1.] 1.1 L'idea di grafo. 1.2 Vertici,cammini,cicli. 1.3 Cammini euleriani e hamiltoniani. Automorfismi di grafi.
1.4 Alcuni invarianti fondamentali. 1.5 Grafi diretti.
[Capitolo 2.] 2.1 Il principio dei cassetti. 2.2 Catene e anticatene . 2.3 Geometrie finite. 2.4 Insieme delle parti. Grafi di Kneser.
[Capitolo 3.] 3.1 Alberi e minimo connettore. 3.2 Grafi planari. 3.3 Grafi bipartiti.
[Capitolo 4.] 4.1 Reti e flussi. 4.2 Connettivit\`a e Teorema di Menger. 4.3 Fattori.
[Capitolo 5.] 4.1 Colorazione dei vertici. 5.2 Colorazioni dei lati . 5.3 L-colorazioni . 5.4 Grafi perfetti.
[Capitolo 6.] 6.1 Teoremi di Ramsey per grafi. 6.2 Teoremi di Ramsey per insiemi. 6.3 Alcune applicazioni.
[Capitolo 7.] 7.1 Grafi regolari. 7.2 Matrice di adiacenza. 7.3 Grafi di Cayley e altri grafi associati a gruppi finiti.
Il programma potrà subire variazioni in itinere. Le dispense potranno essere aggiornate.