GE460- Teoria dei Grafi - a.a. 2020/21

                                                    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. 26/02. (3 ore) Esempi di famiglie di grafi. Grafi regolari. Le matrici di incidenza e adiacenza. Definizione e esempi.  Nozione di isomorfismo di grafi e automorfismo di un grafo. Esempi e il caso di un grafo semplice. Operazioni sui grafi: unione, connettività. Grafi diretti o orientati: definizione e proprietà basiche.
3. 02/03. Sottografi, eliminazione di vertici e lati di un grafo. Un grafo in cui il grado minimo di tutti i vertici è almeno uguale a 2 contiene un ciclo. Cammini e cicli di Hamilton, enunciato del teorema di Rédei. Differenza simmetrica tra grafi. Decomposizioni di un grafo e decomposizione in cicli, grafi pari. Teorema di Veblen: un grafo è pari se e solo se ammette una decomposizione in cicli.
4. 05/03. (3 ore) Sottografi indotti da un'insieme di vertici. Tagli di lati e tagli minimali. Taglio associato a un sottoinsieme di vertici X. Un grafo G è pari se e solo se la cardinalità del taglio associato a X è pari, per ogni sottoinsieme di vertici X di V(G). La differenza simmetrica di tagli è un taglio. Un sottoinsieme di lati è un taglio minimale se e solo se è unione disgiunta di una insieme di tagli minimali. In un grafo connesso il taglio associato a un sottoinsieme di vertici X è minimale se e solo se sono connessi i sottografi indotti G[X] e G[V\X].
5. 09/03. Sottografi pari. Un sottografo è pari se e solo è una unione disgiunta di cicli. Lo spazio vettoriale dei lati di un grafo e i sottospazi dei cicli e dei tagli. Grafi connessi: nozione di passeggiata, diverse caratterizzazioni di componenti connesse. Nozione di ponte (lato di taglio) e prime proprietà.
6. 12/03. (3 ore) Passeggiate Euleriane. Un grafo è Euleriano se e solo se è connesso e pari. L'algoritmo di Fleury. Alberi e floreste. Prime proprietà.
Applicazioni semplici di Teoria dei grafi: Il Lemma di Sperner e il teorema dei 5 colori. Seminario a cura della studentessa Barbara Galati.
7. 16/03. Alberi. Due vertici in un'albero sono connessi da esattamente un cammino. Diverse caratterizzazioni della nozione di albero.
8. 19/03. (3 ore) Alberi generanti: esempi e proprietà. Un grafo è connesso se e solo se contiene un'albero generante. Un grafo è bipartito se e solo se non contiene alcun ciclo di lunghezza dispari. Il numero di alberi generanti diun grafo connesso. Cicli fondamentali in un grafo. Dato un albero, ogni sottografo pari corrisponde in modo unico a un sottoinsieme del rispettivo co-albero. Ogni grafo pari si esprime in modo unico come differenza simmetrica di cicli fondamentali. Esercizi (esercitazione 2).
9. 23/03. Tagli minimali fondamentali. Corrispondenza tra sottoinisiemi di lati di un'albero e tagli del grafo. Introduzione alla teoria delle matroide.
10.  26/03. Grafi non separabili e vertici di taglio. In un grafo connesso con almeno 3 vertici non esistono vertici di taglio se e solo se ogni coppia di vertici è connessa da almeno due cammini internamente disgiunti. Il teorema di Cayley: seminario a cura dello studente Antonello D'Angelli.(pptx)
11. 30/03. Vertici separanti. Un grafo connesso è non separabile se e solo se ogni coppia di lati appartiene a un ciclo commune.  Alberi minimali in un grafo e algoritmi di ricerca: Boruvka, Kruskal e Prim; Seminario a cura della studentessa Helena Rivera Dallorto.
12. 09/04. (3 ore) Decomposizione in blocchi di un grafo e alcune proprietà. Esercitazione 3. Teoremi di Ramsey con un'approccio della logica (teorema della compatezza), seminario a cura dello studente Raffaele di Donna.
13. 13/04. Connettività per vertici. Definizioni e prima proprietà. Relazione con insiemi di vertici di taglio e teorema di Whitney.
14. 16/04. (3 ore). Connetività per vertici. Il lemma del ventaglio e il teorema di Dirac. Il teorema di Max-Flow Min-Cut e applicazioni, seminario a cura della studentessa Melissa Sordi. Il teorema di Menger (nelle sue varie versioni), seminario a cura della studentessa Francesca Percario.
15. 20/04. Grafi 3-connessi. Dato un grafo 3-connesso è possibile scegliere un suo lato la cui contrazione sia ancora 3-connesso. Grafi planari, considerazioni topologiche. I grafi K_5 e K_3,3 non sono planari.
16. 23/04. (3 ore) Identificazione tra grafi planari e grafi rappresentabile nella sfera. Facce di un grafo planare. Algoritmi di visita in un grafo, seminario a cura della studentessa Chiara Stortini. Complessità degli algoritmi, seminario a cura della studentessa Martina Gusai.
17. 26/04. Dualità per grafi planari. Dualità geometrica e proprietà. Dualità tra spazi di cicli e di tagli per grafi planari.
18. 30/04. (3 ore). Relazione tra duali algebrici e duali geometrici: il teorema di Whitney. La formula di Eulero e applicazioni. Grafi in altre superficie topologiche, seminario a cura della studentessa Giusi Capobianco.
19. 04/05. Dualità tra la eliminazione di un lato e la contrazione del suo lato duale per un grafo planare. Esercitazione 4.
20. 07/05. (3 ore). Introduzione alla teoria delle matroidi. Assiomatizzazione della nozione di indipendenza e esempi. Basi di una matroide e equivalenza tra gli assiomi di base e quelli di insiemi indipendenti. Circuiti di una matroide, proprietà e definizione di una matroide a partire della colezione dei suoi circuiti.
21. 11/05.  Circuiti fondamentali associati a una base di una matroide. Nozione di isomorfismo tra matroidi. Matroide grafiche, cografiche, rappresentabili, binarie, ternarie  e regolari. Altriesempi di matroidi e nozioni basiche. Esercizi.
22. 14/05. (3 ore) La funzione rango in una matroide e sue proprietà. Matroide definita a partire della funzione rango. Esempi. L'operatore di chiusura in una matroide e sue proprietà. Matroide definita a partire di un'operatore che soddisfi le proprietà dell'operatore di chiusura. Esercizi.
23. 18/05. Definizioni e esempi di sottoinsiemi chiusi, generanti e iperpiani. Matroide di Fano: definizione e proprietà. Matroidi trasversali.  L'algoritmo Greedy per le matroidi.
24. 21/05. (3 ore) Caratterizzazione delle matroidi a partire dell'algoritmo Greedy, applicazioni a matroidi trasversali e problemi di "matchings" con prioritá. Matroide duale: definizione e prime proprietà. Teoria di Ramsey, seminario a cura della studentessa Maria Concetta Campailla.
25. 25/05. Dualità per matroide: esempi e proprietà. Grafi due isomorfi e il teorema di Whitney: due matroide grafiche sono isomorfe se e solo se i corrispondenti grafi sono 2-isomorfi, seminario a cura dello studente Michele Matteucci.
26. 28/05. (3 ore) Dualitá per matroidi grafiche, un grafo è planare se e solo se la sua matroide grafica è cografica. Dualità per matroidi rappresentabili e regolari. Catene di Markov, seminari a cura delle studentesse Sara Giuli e Francesca Giulianelli.