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.
Altre Informazioni
Il corso è presente sulla piattaforma Moodle
Modalità di verifica apprendimento
Esame orale preceduto da un esercizio scritto. 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.