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.