GE460- Teoria dei Grafi - a.a.
2021/22
DIARIO DELLE
LEZIONI
1. 23/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. Esercizi del foglio di esercizi 1.
3. 02/03. 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. 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.
4. 05/03. (3 ore) 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.Sottografi indotti da un'insieme di vertici. Tagli di
lati. Taglio associato a un sottoinsieme di vertici X. Esercizi del foglio di esercizi 1.
5. 09/03. Tagli e tagli minimali. 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].
6. 11/03. (3 ore) 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à.
7. 16/03. Passeggiate
Euleriane. Un grafo è Euleriano se e solo se è connesso e
pari. L'algoritmo di Fleury. Alberi e floreste. Prime proprietà.
Due vertici in un'albero sono connessi da esattamente
un cammino.
8. 18/03. (3 ore) Diverse caratterizzazioni della nozione di albero. 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.
9. 23/03. Il numero di alberi generanti di un 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.
10. 25/03. (3 ore) Tagli minimali
fondamentali. Corrispondenza tra sottoinisiemi di lati di un'albero e
tagli del grafo. Introduzione alla teoria delle matroide. Esercizi.
11. 30/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.Vertici separanti e grafi non separabili.
12. 01/04. (3 ore) Decomposizione in blocchi di un grafo e alcune proprietà. Connettività
per vertici. Definizioni e prima proprietà. Esercizi.
13. 06/04. Connettività
per vertici. Connettività locale e Teorema di Menger.
14. 08/04. (3 ore). Connettività per vertici. Relazione con
insiemi di vertici di taglio e teorema di Whitney.
15. 27/04. Grafi planari,
considerazioni
topologiche. I grafi K_5 e K_3,3 non sono planari.Identificazione tra
grafi planari e grafi rappresentabile nella sfera. Facce di un grafo
planare.
16. 29/04. (3 ore) Dualità per
grafi planari. Dualità geometrica e proprietà.
Dualità tra spazi di cicli e di tagli per grafi planari. Esercizi
17. 04/05. Relazione tra duali algebrici e duali geometrici: il teorema di Whitney. La formula di Eulero e applicazioni.
Dualità tra la eliminazione di un lato e la contrazione del suo lato duale per un grafo planare.
18. 06/05. La formula di Eulero per Poliedri e grafi: seminario a cura dello studente Luca Dragone. Esercizi
19. 11/05.
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.
20. 13/05. (3 ore) Circuiti
fondamentali associati a una base di una matroide. Nozione di
isomorfismo tra matroidi. Matroide grafiche, cografiche,
rappresentabili, binarie, ternarie e regolari. Altri esempi di matroidi e nozioni basiche. Esercizi.
21. 18/05. La funzione rango su una matroide e proprietà. Caratterizzazione di unna matroide usando la funzione rango. Esempi.
22. 20/05.
23. 25/05.
24. 27/05.
25. 01/06.
27. 08/06.
28. 10/06.