A.A. 2012-2013 Teoria dei grafi
Docente: LUCIA CAPORASO -
Ricevimento: Lunedi e mercoledi 13-14
Ufficio: 108 -
Tel: 06 5733 8040 - E-mail: caporaso--at--mat.uniroma3.it
Programma di massima:
Definizioni di base.
Connettività .
Grafi planari
Coloramenti.
Flussi.
Prerequisiti:
Algebra lineare (GE110)
Geometria e topologia di spazi euclidei (GE210, GE220).
Testi consigliati:
R. Diestel Graph theory Spriger GTM 173
Lezioni: Lunedi e mercoledi 11-13 aula 9.
Prima lezione: 24/09/2012
Esami: Esame scritto: 28/01/2013 Testo esame con soluzioni
Esame Orale A:
29/01/2013 ore 15:30 studio 108.
Esame Orale B: 13/02/2013 ore 11:00 studio 108. Obbligatorio prenotarsi entro il 10/02/2013 tramite messaggio email a caporaso@mat.uniroma3.it
Diario giornaliero delle lezioni:
(1,2) 24/9 : Definizioni di grafo (semplice), valenza di un vertice,
cinta e circonferenza di un grafo. Esempi. Grafi completi.
Cammini e cicli contenuti in un grafo.
Esistenza di cammini e cicli in relazione alla valenza minima di un grafo. Distanza tra vertici. Grafi connessi.
(3,4) 26/9 :
Diametro di un grafo.
Grafi euleriani e Teorema di Eulero sulla caratterizzazione di grafi euleriani.
Alberi e Teorema di caratterizzazione di alberi.
(5,6) 1/10 :
Ordinamenti sui vertici di un grafo. Caratterizzazione
di alberi tramite la relazione tra numero di vertici e di lati. Alberi radicati.
Sotto alberi generanti normali in un grafo. Connessione e connettività per vertici. Esempi.
Esercizi. Capitolo 1: 1,5,15,18.
Soluzioni a cura del dott. Daniele Piras.
(7,8) 3/10 : Connessione e connettività per lati.
Teorema di esistenza di alberi generanti normali per grafi qualsiasi; costruzione di
tali alberi. Multigrafi. Grafi bipartiti: definizione ed esempi.
(9,10) 8/10 : Caratterizzazione di grafi bipartiti. Spazi vettoriali associati a un grafo:
spazio dei lati, spazio dei vertici,
spazio dei cicl e sue proprietà . Definizione di taglio.
Esercizi. Capitolo 1: 1, 20, 26, 29. Soluzioni a cura del dott. Daniele Piras.
(11,12) 15/10 : Spazio dei tagli di un grafo: generatori e dimensione; relazione con lo spazio dei cicli.
Calcolo del numero ciclomatico.
Matrice di incidenza e matrice adiacenza.
(13,14) 17/10 :
Accoppiamento (matching) e Copertura tramite vertici in un grafo: definizioni ed esempi.
Studio per grafi bipartiti: Teorema di König e Teorema del matrimonio.
Esercizi. Capitolo 2: 3,4. Soluzioni a cura del dott. Daniele Piras.
(15,16) 22/10 :
Conseguenze del Teorema del matrimonio sull'esistenza di 1-fattori e 2-fattori.
Discussione e dimostrazione del Criterio di Tutte per l'esistenza di 1-fattori in grafi qualsiasi.
(17,18) 24/10 : Esistenza di 1-fattori per grafi cubici.
Grafi orientati. Teorema di Gallai-Milgram per le coperture in cammini di grafi orientati.
Esercizi. Capitolo 2: 11,14
(19,20) 29/10 :
Risultato di Dilworth (corollario 2.3.2). Grafi 2-connessi: grafo a blocchi, caratterizzazione di grafi 2-connessi (Prop. 3.1.2).
Contrazione di lati ed esempi riguardanti i grafi 3-connessi.
Esercizi. Capitolo 2: 16. Capitolo 3: 6,7. Soluzioni a cura del dott. Daniele Piras.
(21,22) 5/11 : Contrazione di lati in grafi 3-connessi. Teorema di Tutte di caratterizzazione di grafi 3-connessi: dimostrazione e illustrazione.
Generatori dello spazio dei cicli in grafi 3-connessi e non 3-connessi. Esempi.
(23,24) 7/11:
Terema di Tutte sullo spazio dei cicli di un grafo 3-connesso: dimostrazione in un caso particolare.
Teorema di Menger, discussione e dimostrazione.
Esercizi. Capitolo 3: 9,10,11. Soluzioni a cura del dott. Daniele Piras.
(25,26) 7/11:
Connettività : conseguenze del
Teorema di Menger. Grafo linea di un grafo: definizione e proprietà .
(27,28) 7/11:
Connettività per lati e Teorema di Menger.
Teorema di Menger globale.
Esistenza di alberi generanti disgiunti in grafi connessi per lati.
Enunciato e casi semplici del teorema di Tutte e Nash-Williams.
Esercizi. Capitolo 3: 14, 15. Soluzioni a cura del dott. Daniele Piras.
(29,30) 19/11:
Dimostrazione del teorema di Tutte e Nash-Williams.
(31,32) 21/11:
Partizioni di grafi in sotto grafi. Teorema di Nash-Williams.
Contrazioni, e minori di grafi. Suddivisioni, e loro relazione con i minori.
Applicazione a grafi cubici 3-connessi.
(33,34) 26/11: Richiami di topologia riguardanti il piano euclideo.
Grafi planari. Definizione, esempi e proprietà di base.
(35,36) 28/11: Facce di
grafi planari: caso di foreste, cicli e grafi 2-connessi.
Grafi massimali e triangolazioni. Enunciato della formula di Eulero ed applicazioni.
Esercizi. Capitolo 4: 1,2,3. Soluzioni a cura del dott. Daniele Piras.
(37,38) 3/12: Interpretazione della formula di Eulero attraverso il numero ciclomatico, o genere, di un grafo.
Dimostrazione della formula di Eulero. Caratterizzazione di facce per grafi planari 3-connessi.
Isomorfismi astratti e isomorfismi topologici per grafi planari.
(39,40) 5/12: Isomorfismi topologici e combinatoriali di grafi planari. Teorema di Whitney sull'equivalenza di immersioni planari per grafi 3-connessi.
Grafi contenenti K^5 o K_{3,3} come minori o come minori topologici.
Esercizi. Capitolo 1: 23. Capitolo 4: 4,5,9,11 Soluzioni a cura del dott. Daniele Piras.
(41,42) 10/12: Caratterizzazione di grafi 3-connessi planari; teorema di Kuratowski.
Caratterizzazione algebrica di grafi planari: Teorema di Mac Lane e sue conseguenze.
(43,44) 12/12: Dualità planare e dualità astratta. Teorema di Whitney sulla caratterizzazione di grafi planari.
Esercizi. Capitolo 4: 28, 29, 32 Soluzioni a cura del dott. Daniele Piras.
(45,46) 17/12: Colorazioni di grafi e numero cromatico di un grafo. Stime sul numero cromatico tramite la valenza massima e minima: teorema di Brooks.
(47,48) 19/12: Colorazioni di grafi planari e stime del numero cromatico di un grafo planare. Teorema dei cinque colori.