GE460- Teoria dei Grafi - a.a. 2017/2018

                                                    DIARIO DELLE LEZIONI


1.  28/09 Introduzione al corso. Grafi: definizioni basiche. Grafi semplici o no, planarita', connetivita', grado, regolarita', matrici di incidenza e di adiacenza. Esempi di famiglie di grafi. Il ''handshaking lemma''.

2.  03/10 Ancora esempi di famiglie di grafi.  Grafi ottenuti a partire da altri: complemento, sottografo, cancellazione e contrazione. Isomorfismi e automorfismi di grafi. Connetivita': cammini, cicli. Un grafo e' bipartito se e soltanto se ogni ciclo ha lunghezza pari.

3.  05/10 Connetivita' e componente connesse. Connettivita' per lati e per vertici. Grafi Euleriani e semi-Euleriani.

4.  10/10 Teorema di Euler: un grafo connesso e' Euleriano se e soltanto se ogni vertice ha grado pari. Grafi Hamiltoniani. Condizioni sufficienti per garantire che un grafo e' Hamiltoniano: i teoremi di Ore e di Dirac.

5.  12/10 Dimostrazione del teorema di Ore. Alberi e foreste. Il numero ciclomatico e il "cutset" rank di un grafo.

6.  17/10 Sistema fondamentali di cicli e di tagli associati a una foresta generante. Enumerazione di foreste generanti. Il teorema di Cayley.

7.  19/10 Alberi generanti: l'algoritmo "greedy" per il "connector problem". Grafi planari.  K3,3 e K5 non sono planari. Enunciato del teorema du Kuratovski e variazioni.

8.  24/10 Formula di Euler per grafi planari. Il duale di un grafo planare.

9.  25/10 Corrispondenza tra cicli e tagli per grafi planari e il loro duale. Duale astratto. Un grafo che ammette un duale astratto e' planare. Coloramenti: considerazioni iniziali e alcune proprieta'.

10. 31/10 Coloramenti: il teorema dei 5 colori. Grafi su superfici: classificazione delle superficie topologica presentazione a carico dello studente Stefano Serpente.

11. 02/11 Coloramenti di faccie e dualita' tra questo problema e il coloramento di vertici. Riduzione della dimostrazione del teorema dei 4 colori ai coloramenti di faccie di grafi cubici. ''The marriage problem": il teorema di Hall.

12. 14/11 Teorema di Hall nel linguaggio dei trasversali. Criteri di esistenza di trasversali e trasverzali parziali. Applicazione alla costruzione di quadrati latini. Grafi diretti: nozione basiche e orientabilita'.

13. 21/11 Il teorema di Max-Flow Min-Cut e il Teorema di Menger: presentazione a carico dello studente Lucio Zaccardeli.

14. 22/11 Complessita'  di algoritmi e applicazioni a Teoria dei Grafi: presentazione a carico dello studente Daniele Salierno.

15. 23/11 Introduzione alla teoria dei matroidi: definizioni usando basi e elementi indipendenti. Matroidi grafici e cografici, matroidi vettoriali e il problema della rappresentabilita'.

16. 28/11 Definizione di matroide utilizzando i cicli e la funzione rango.  Minori di un matroide. Matroidi trasversali e il Teorema di Rado per i matroidi.

17. 30/11 Unione di matroidi e applicazioni: esistenza di basi disgiunte in un matroide. Dualita' per matroidi e applicazioni ai matroidi grafici e cografici. Matroidi planari e la generalizzazione del teorema di Kuratovski per matroidi: presentazione a carico dello studente Pierpaolo Colage'.

18. 05/12 Elementi di teoria algebrica dei grafi: la matrice di incidenza e la matrice laplaciana di un grafo orientato. Lo spazio dei vertici e lo spazio dei lati di un grafo. Sottospazio dei cicli e sottospazio dei tagli di un grafo orientato definito della matrice di incidenza.

19. 07/12 Basi per lo spazio dei cicli e per lo spazio dei tagli di un grafo. Il teorema di Riemann-Roch per grafi: presentazione a carico dello studente Gaudencio Falcone.

20. 12/12 Dimostrazionde del "Matrix Tree theorem generalizzato". L'agoritmo di contrazione/restrizione per matroidi. Esempi. Il numero di orientazioni acicliche di un grafo.

21. 14/12 Ancora polinomi per grafi: il polinomio cromatico, il polinomio di "reliabiliaty". Esempi. Il polinomio rango (o di Tutte) di un matroide. Poprieta' e prime applicazioni.

22. 19/12 Dimostrazione del teorema di struttura per funzioni sui matroidi che soddisfano proprieta' di contrazione/restrizione. La loro scrittura attraverso il polinomio rango.
Mosse di Whitey e due isomorfismo per grafi. Isomorfismo tra matroidi grafici implica isomorfismo tra grafi nel caso in cui i grafi siano 3 connessi.

23. 20/12 Il Teorema di Whitney per matroidi grafici: sketch della dimostrazione. Caratterizzazione per minori esclusi da matroidi binari e regolari. Il teorema di Seymour.