Università Roma Tre

Grafi: definizioni basiche. Grafi semplici o no, planarita', connetivita', grado, regolarita', matrici di incidenza e di adiacenza. Esempi di famiglie di grafi. Il ''handshaking lemma''.
Grafi ottenuti a partire da altri: complemento, sottografo, cancellazione e contrazione. Isomorfismi e automorfismi di grafi. Connetivita': cammini, cicli. Un grafo e' bipartito se e soltanto se ogni ciclo ha lunghezza pari.
Connetivita' e componente connesse. Connettivita' per lati e per vertici. Grafi Euleriani e semi-Euleriani.
Teorema di Euler: un grafo connesso e' Euleriano se e soltanto se ogni vertice ha grado pari. Grafi Hamiltoniani. Condizioni sufficienti per garantire che un grafo e' Hamiltoniano: i teoremi di Ore e di Dirac.
Dimostrazione del teorema di Ore. Alberi e foreste. Il numero ciclomatico e il "cutset" rank di un grafo.
Sistema fondamentali di cicli e di tagli associati a una foresta generante. Enumerazione di foreste generanti. Il teorema di Cayley.
Alberi generanti: l'algoritmo "greedy" per il "connector problem". Grafi planari. K3,3 e K5 non sono planari. Enunciato del teorema du Kuratovski e variazioni.
Formula di Euler per grafi planari. Il duale di un grafo planare.
Corrispondenza tra cicli e tagli per grafi planari e il loro duale. Duale astratto. Un grafo che ammette un duale astratto e' planare. Coloramenti: considerazioni iniziali e alcune proprieta'.
Coloramenti: il teorema dei 5 colori. Grafi su superfici: classificazione delle superficie topologiche.
Coloramenti di faccie e dualita' tra questo problema e il coloramento di vertici. Riduzione della dimostrazione del teorema dei 4 colori ai coloramenti di faccie di grafi cubici. ''The marriage problem": il teorema di Hall.
Teorema di Hall nel linguaggio dei trasversali. Criteri di esistenza di trasversali e trasverzali parziali. Applicazione alla costruzione di quadrati latini. Grafi diretti: nozione basiche e orientabilita'.
Il teorema di Max-Flow Min-Cut e il Teorema di Menger.
Complessita' di algoritmi e applicazioni a Teoria dei Grafi.
Introduzione alla teoria dei matroidi: definizioni usando basi e elementi indipendenti. Matroidi grafici e cografici, matroidi vettoriali e il problema della rappresentabilita'.
Definizione di matroide utilizzando i cicli e la funzione rango. Minori di un matroide. Matroidi trasversali e il Teorema di Rado per i matroidi.
Unione di matroidi e applicazioni: esistenza di basi disgiunte in un matroide. Dualita' per matroidi e applicazioni ai matroidi grafici e cografici. Matroidi planari e la generalizzazione del teorema di Kuratovski per matroidi.
Elementi di teoria algebrica dei grafi: la matrice di incidenza e la matrice laplaciana di un grafo orientato. Lo spazio dei vertici e lo spazio dei lati di un grafo. Sottospazio dei cicli e sottospazio dei tagli di un grafo orientato definito della matrice di incidenza.
Basi per lo spazio dei cicli e per lo spazio dei tagli di un grafo. Il teorema di Riemann-Roch per grafi.
Dimostrazionde del "Matrix Tree theorem generalizzato". L'agoritmo di contrazione/restrizione per matroidi. Esempi. Il numero di orientazioni acicliche di un grafo.
Ancora polinomi per grafi: il polinomio cromatico, il polinomio di "reliabiliaty". Esempi. Il polinomio rango (o di Tutte) di un matroide. Poprieta' e prime applicazioni.
Dimostrazione del teorema di struttura per funzioni sui matroidi che soddisfano proprieta' di contrazione/restrizione. La loro scrittura attraverso il polinomio rango.
Mosse di Whitey e due isomorfismo per grafi. Isomorfismo tra matroidi grafici implica isomorfismo tra grafi nel caso in cui i grafi siano 3 connessi.
Il Teorema di Whitney per matroidi grafici: sketch della dimostrazione. Caratterizzazione per minori esclusi da matroidi binari e regolari. Il teorema di Seymour.

R. Diestel: Graph theory, Spriger GTM 173.
R. Wilson: Introduction to Graph theory, Prentice Hall.
B. Bollobas: Modern Graph theory, Springer GTM 184.
J. A. Bondy, U.S.R. Murty: Graph theory, Springer GTM 244.
N. Biggs: Algebraic graph theory, Cambridge University Press.
C. D. Godsil, G. Royle: Algebraic Graph theory, Springer GTM 207.
J. G. Oxley: Matroid theory. Oxford graduate texts in mathematics, 3.