GE460- Teoria dei Grafi - a.a. 2019/20

                                                    DIARIO DELLE LEZIONI


1. 24/02. Introduzione al corso. Grafi: definizioni basiche. Grafi semplici o no, planarita', connetivita', grado. Esempi di famiglie di grafi. Il ''handshaking lemma''.
2. 28/02. Grafi regolari. Le matrici di incidenza e adiacenza. Definizione e esempi. Dimostrazione del "handshaking lemma" usando ma matrice di incidenza. Nozione di isomorfismo di grafi e automorfismo di un grafo. Esempi e il caso di un grafo semplice. Operazioni sui grafi: unione, intersezione, complementare, eliminazioni di lati e vertici.
3. 02/03. Sottografi e cicli. Un grafo in cui ogni vertice ha grado almeno due ha almeno un ciclo; un grafo è bipartito se e soltanto se ogni ciclo ha lunghezza pari e il Teorema di Veblen: un grafo ammette una decomposizione in cicli se e soltanto se è un grafo pari.
4. 02/03. Esercitazione 1: nozioni basiche e esempi di grafi.
5. 13/03. Lezione online 1: Sottografi, operazioni sui grafi. Link: https://drive.explaineverything.com/thecode/QBREYXQ
6. 13/03. Lezione online 2: Tagli e tagli minimali su un grafo. Link: https://drive.explaineverything.com/thecode/ULAFZNE
7. 16/03. Lezione online 3. Sottografi pari e spazi di cicli e tagli in un grafo. Link: https://drive.explaineverything.com/thecode/HTACZBW.
8. 22/03. Lezione online 4. Grafi connessi e camminate Euleriane. Link: https://drive.explaineverything.com/thecode/NVJPPHS.5
9. 27/03. Lezione online 5: Alberi e foreste. Link:  https://drive.explaineverything.com/thecode/MGJEPJF
10. 03/04. Lezione online 6: Alberi generanti e il loro numero. Link: https://drive.explaineverything.com/thecode/GNXNEBP
11. 04/04. Lezione online 7: Grafi orientati e il Teorema di Cayley. Link: https://drive.explaineverything.com/thecode/GYKHKDH
12. 06/04. Lezione online 8. Cicli fondamentali, tagli minimali fondamentali e introduzione alle matroide. Link: https://drive.explaineverything.com/thecode/AEPBTDZ
13. 15/04. Lezione online 9. Grafi non separabili: vertici separanti e di taglio e decomposizione in blocchi di un grafo. Link: https://drive.explaineverything.com/thecode/GQWPSQC
14. 23/04. Lezione online 10. Connettività (per vertici). Il teorema di Menger (versione per vertici e grafi non orientati). Grafi 3-connessi e loro prorietà. Link: https://drive.explaineverything.com/thecode/LHCMSLP
14. 02/05. Lezione online 11. Grafi planari. Prime consideriazioni e la formula di Eulero. Link: https://drive.explaineverything.com/thecode/BNWYRSY
15. 04/05. I "proof-nets" e i grafi nella logica: seminario valido per la valutazione in itinere, tenuto da Elettra Cesareo.
16. 09/05. Lezione online 12. Dualità per grafi planari. Link: https://drive.explaineverything.com/thecode/SVPKBUZ
17. 11/05. ''Network Flows'' e il teorema/algoritmo di max-flow, min-cut. Seminario valido per la valutazione in itinere, tenuto da Giancarlo Stabile.
18. 11/05. ''Tree search algorithms'': esposizione e esempi di implementazioni in C. Seminario valido per la valutazione in itinere, tenuto da Alberto Cicciarelli.
19. 14/05. Matroidi: introduzione e prime proprietà. Assiomi di basi, indipendenti e di circuiti. Esempi. Link: https://drive.explaineverything.com/thecode/WUVUYAN
20. 19/05. Matroidi2: esempi vari e loro proprietà e la nozione di rango di un sottoinsieme di una matroide. La definizione di una matroide usando la nozione di rango. Link: https://drive.explaineverything.com/thecode/UKHVPGH
21. 22/05. Algoritmi per grafi: Seminario valido per la valutazione finale tenuto da Cecilia Giombi.
22. 27/05. Chiusura per matroidi e esempi: matroidi cografici, trasversali, bipartiti e Euleriani. Link: https://drive.explaineverything.com/thecode/EEGEYCJ
23. 27/05. L'algoritmo Greedy per matroidi e applicazioni. Link:  SoluzioniPYVNDMZ
24. 01/06. Grafi in altre superficie. Seminario valido per la valutazione finale tenuto da Mattia Pascuttini.
25. 01/06. Il teorema della matrice di Kirchhoff. Seminario valido per la valutazione finale tenuto da Silvio di Gregorio.
26. 04/06. Dualità per matroidi. Definizione, proprietà e esempi. Link: https://drive.explaineverything.com/thecode/GDGEXBG
27. 05/06. Il Teorema di Kuratowski. Seminario valido per la valutazione finale tenuto da Sara Prevete.
28. 05/06. Colorazioni per grafi. Seminario valido per la valutazione finale tenuto da Benedetta Poles.
29. 07/06. Dualità per matroide grafiche. Caratterizzazione di matroide grafiche e cografiche. Questioni riguardanti la rappresentailità, dualità di matroide rappresentabili e enunciato del Teorema di Whitney. Link: https://drive.explaineverything.com/thecode/ECTPXDL
30. 17/07. ``Matchings'' e il problema del matrimonio stabile. Teorema di Hall, generalizzazioni e algoritmi. Seminario valido per la valutazione finale tenuto da Beatrice Bernardini.