Insegnamento mutuato da: B018796 - TEORIA DEI GRAFI E COMBINATORIA Laurea Magistrale in MATEMATICA Curriculum APPLICATIVO
Lingua Insegnamento
Italiano
Contenuto del corso
Introduzione alla teoria dei grafi: concetti fondamentali, grafi euleriani e hamiltoniani, alberi; grafi planari, grafi regolari, grafi bipartiti.Grafi diretti e connettivita'; reti e flussi. Colorazioni. Teoria di Ramsey.Teoria estremale degli insiemi.Teoria algebrica dei grafi.
Acquisire conoscenze su alcuni risultati di base delle teoria dei grafi e della combinatoria, cosi' come di alcune tecniche dimostrative usate in tali ambiti.
Prerequisiti
Corsi raccomandati: Algebra 1 e Algebra 2.
Metodi Didattici
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attività formative di tipo individuale: 155
Numero di ore relative alle attività in aula: 70
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Martedi': 14.30-16.00
Giovedi': 14.00-15.30
Studio 39 - Dipartimento di Matematica e Informatica "U. Dini"
Modalità di verifica apprendimento
Prova orale
Programma del corso
1. Concetti di base della Teoria dei Grafi.
Grafi e multigrafi. Isomorfismo di (multi)grafi.
Prime classi di grafi.
Grafo di Petersen. Sottografi e sottografi indotti. Grafi complementari.
Grafi hamiltoniani. Teoremi di Ore e di Dirac. Il grafo di Petersen non e' hamiltoniano.
Alcuni invarianti: distanza, diametro, indice di stabilita',
numero cromatico.
Problemi di Teoria Estremale dei grafi. Grafi $r$-partiti e grafi di Turan.
Teorema di Turan.
2. Alberi e grafi bipartiti. Accoppiamenti. 1-fattori.
Alberi e foreste. Spanning trees minimali.
Grafi bipartiti. Teoremi di Hall (dei matrimoni; SDR; SDR 'simultanei').
Teorema di Birkhoff-VonNeumann. Coperture. Teorema di Koenig.
Algoritmo ungherese. 1-fattori. Teorema di Tutte.
2-fattori; Teorema di Petersen. Grafi piani e planari.
3. Colorazioni
Grafi planari. Teorema di Kuratowski. Teorema dei 5 colori.
Colorazioni. Teorema di Brooks.
L-colorazioni. Teorema di Thomassen.
Grafi perfetti.
Colorazioni dei lati; indice cromatico. Teorema di Koenig.
Teorema di Vizing.
4. Reti e Flussi. Connettivita'
Grafi diretti; definizioni e proprieta' di base.
Reti e flussi. Teorema MaxFlow-MinCut.
Connettivita'. Teoremi di Menger.
5. Teoria algebrica dei grafi
Matrici di adiacenza; spettro. Operatore di Laplace.
Automorfismi di grafi. Grafi vertex-transitivi e edge-transitivi. Punti fissi di
automorfismi di alberi. Grafi di Calyey.
6. Teoria Estremale degli insiemi
Delta-sistemi e Lemma del girasole.
Intersecting families e ultrafiltri.
Principio dei cassetti; lemma di Dirichlet; Teorema di Schur
ed applicazioni.
Famiglie uniformi intersecanti. Teorema di Erdos-Ko-Rado.
Applicazioni alla geometria proiettiva finita.
Famiglie di Sperner.
Decomposizione di un insieme parzialmente ordinato come unione di catene / anticatene. Teorema di Dilworth.
7. Teoria di Ramsey
Numeri di Ramsey e loro limitazioni. Teoremi di Ramsey. Applicazioni.