GE460- Teoria dei Grafi - a.a. 2022/23

                                                    DIARIO DELLE LEZIONI

1. 20/02. Introduzione al corso. Grafi: definizioni basiche. Grafi semplici o no, planarita', connetivita', grado.  Il ''handshaking lemma''.

2. 21/02. Esempi di famiglie di grafi. Grafi regolari. Le matrici di incidenza e adiacenza. Definizione e esempi. 

3. 24/02. Nozione di isomorfismo di grafi e automorfismo di un grafo. Esempi e il caso di un grafo semplice. Operazioni sui grafi: unione, connettività.  Esercizi del foglio di esercizi 1.

4. 27/02. Grafi diretti. Sottografi. Un grafo i cui tutti i vertici hanno grado almeno 2 ha un ciclo. Esercizi del foglio di esercizi 1.

5. 28/02. Sottografi, grafi indotti. Teorema di Veblen: un grafo è pari se e soltanto se ammette una decomposizione in cicli. Esercizi del foglio di esercizi 1.

6. 03/03. Differenza simmetrica di grafi generanti. Tagli e tagli minimali. La differenza simmetrica di tagli è un taglio.  Un grafo è pari se e soltanto se ogni suo taglio è pari. Esercizi del foglio di esercizi 1.

7. 06/03. Un taglio è unione disgiunta 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]. La differenza simmetrica di grafi pari è pari. Un sottografo pari interseca ogni ciclo in un numero pari di lati. Esercizi del foglio di esercizi 1.

8. 07/03. Lo spazio vettoriale dei cicli e lo spazio vettoriale dei tagli di un grafo. Ponti o lati di taglio. Passeggiate e passeggiate Euleriane; grafi Euleriani. Un grafo Euleriano è pari. Esercizi del foglio di esercizi 1.

9. 10/03. Algoritmo de Fleury: un grafo pari connesso ammette una passeggiata Euleriana. Alberi e foreste: prime proprietà. Formulazioni equivalenti della nozione di albero.

10. 13/03.  Alberi generanti di un grafo. Un grafo è bipartito se e soltanto se ogni suo ciclo ha lunghezza pari. Esercizi.

11. 14/03. Lo spazio dei cicli e lo spazio dei tagli: costruzioni di base date da cicli fondamentali e tagli fondamentali associati alla scelta di un albero generante.

12. 17/03. Risoluzione di esercizi del foglio 1. Introduzione alla teoria delle martoide.