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. Relazionare tale teoria a questioni di combinatoria.
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
L'idea di grafo e multigrafo, grado, lemma stretta di mano, grafi regolari. Teorema di Erdos-Gallai. Automorfismi di grafi e grafo complementare. Sottografi e sottografi indotti. Walks, trials e cammini, circuiti e cicli. Cammini euleriani e hamiltoniani. Teorema di Ore e di Dirac.
Alcuni invarianti fondamentali: diametro e calibro, indice di stabilità, clique number, numero cromatico. Invariati e sottografi.
Il principio dei cassetti. Teorema di Mantel e di Reiman. Catene e anticatene in un poset. Teorema di Dilworth e di Mirsky. Geometrie finite, coefficienti di Gauss. Teoremi sulle geometrie proiettive associate ad un campo. Versione assiomatica di piano proiettivo. Teorema di Bruck e Ryser. Ordine di un piano proiettivo. Piano di Fano.
Alberi e minimo connettore. Algoritmo di Kruskal.
Grafi planari e teorema di Kuratowski. Non planaria di K_5 e K_3,3. Grafo di Petersen come grafo toroidale. Il teorema della mappa a quattro colori.
Grafi bipartiti e loro caratterizzazione. Il problema degli accoppiamenti, il teorema dei matrimoni di Hall. Accoppiamenti massimi e ottimali. Relazione di ordine associata ad un grafo bipartito. Le influenze del teorema di Dilworth. Teorema di Konig.
Grafi diretti e diretti pesati. Reti e flussi. Tagli su reti ed algoritmo dei cammini aumentanti. Teorema di Ford e Fulkerson. Connettività e Teorema di Menger. Problematiche di convergenza del metodo dei cammini aumentanti su reti a capacità reali.
Matrice di adiacenza. Grafi di Cayley e altri grafi associati a gruppi finiti.
Interpretazione di problemi di combinatoria via teoria dei grafi.
Il programma potrà subire variazioni in itinere, legate agli interessi degli studenti. Le dispense potranno essere aggiornate.