2. Docenti
  3. Didattica

TEORIA DEI GRAFI

Fabrizio PUGLIESE TEORIA DEI GRAFI

0512300028
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2020/2021

ANNO CORSO 3
ANNO ORDINAMENTO 2018
PRIMO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
FABRIZIO PUGLIESE T Curriculum
Obiettivi
L'INSEGNAMENTO HA L'OBIETTIVO PRIMARIO DI IMPARTIRE LE NOZIONI FONDAMENTALI DI TEORIA DEI GRAFI.

RISULTATI DI APPRENDIMENTO ATTESI

- CONOSCENZA E CAPACITÀ DI COMPRENSIONE: SCOPO DEL CORSO È DARE ALCUNE CONOSCENZE DI BASE IN TEORIA DEI GRAFI, DI EVIDENZIARNE I LEGAMI CON ALTRI CAMPI DELLA MATEMATICA E DI MOSTRARNE ALCUNE DELLE INNUMEREVOLI APPLICAZIONI. LO STUDIO DEI GRAFI SARÀ L'OCCASIONE, PER LO STUDENTE DI APPRENDERE ALCUNE TECNICHE FONDAMENTALI DI CALCOLO COMBINATORIO E VEDERE ALCUNE SORPRENDENTI APPLICAZIONI DELL'ALGEBRA LINEARE ALLO STUDIO DELLA STRUTTURA DI UN GRAFO;

- CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE: UNO DEGLI OBIETTIVI PRINCIPALI DEL CORSO È DI METTERE LO STUDENTE IN GRADO DI APPLICARE CONCRETAMENTE LE NOZIONI TEORICHE APPRESE. A QUESTO SCOPO VERRANNO SVOLTE NUMEROSE ESERCITAZIONI, NELLE QUALI LO STUDENTE VEDRÀ COME TALI NOZIONI POSSANO APPLICARSI CON SUCCESSO A PROBLEMI PRATICI DELLA NATURA PIÙ VARIA (PROBLEMI DI OTTIMIZZAZIONE, ANALISI DEI FLUSSI NELLE RETI, ALGORITMI DI RICERCA PER IL WEB, ECC.).
Prerequisiti
I PREREQUISITI UTILI SONO LE CONOSCENZE DI BASE DI ALGEBRA LINEARE E ALCUNE CONOSCENZE DI ALGEBRA IMPARTITE NEI CORSI OBBLIGATORI DI GEOMETRIA E ALGEBRA DELLA LAUREA TRIENNALE IN MATEMATICA.
Contenuti
1. NOZIONI DI BASE.

VARI TIPI DI GRAFO. OPERAZIONI SUI GRAFI. ISOMORFISMO FRA GRAFI E GRUPPO DI AUTOMORFISMI DI UN GRAFO. PASSEGGIATE, CAMMINI, CICLI E NOZIONI ASSOCIATE (DISTANZA, DIAMETRO, CALIBRO, CENTRO).

2. CONNETTIVITÀ.

ALBERI E FORESTE; GRAFI BIPARTITI. ALGORITMI SU ALBERI GENERATORI (BREADTH-FIRST, WIDTH-FIRST; DIJKSTRA; KRUSKAL). INSIEMI SEPARATORI E CONNETTIVITÀ; DISEGUAGLIANZA DI WHITNEY. TEOREMA DI MENGER.

3. GRAFI EULERIANI ED HAMILTONIANI.

CIRCUITI EULERIANI E TEOREMA DI EULERO; PROBLEMA DEL POSTINO CINESE, ALGORITMO DI FLEURY. CICLI HAMILTONIANI; TEOREMA DI ORE; CHIUSURA DI UN GRAFO; TEOREMA DI CHVATAL.

4. MATCHINGS.

MATCHING E RICOPRIMENTI; MATCHING MASSIMI E PERFETTI; TEOREMA DI BERGE. MATCHING IN GRAFI BIPARTITI; TEOREMI DI HALL, DI KOENIG, DI TUTTE. MATRIMONI STABILI E ALGORITMO DI GALE-SHAPLEY.

5. RETI E FLUSSI.

FLUSSO IN UNA RETE; TEOREMA "MAX FLOW = MIN CUT", ALGORITMO DI FORD-FULKERSON E ALGORITMO DI EDMONDS-KARP; FLUSSI INTERI; EQUIVALENZA FRA MF-MC, TEOREMA DI HALL E TEOREMA DI MENGER.

6. IMMERSIONI DI GRAFI IN SUPERFICI.

GRAFI PLANARI; FORMULA DI EULERO E SUE APPLICAZIONI; TEOREMA DI KURATOWSKI; TEST DI PLANARITÀ DI DEMOUCRON. GENERE DI UN GRAFO; IMMERSIONE DI K_5 E DI K_3,3 NEL TORO.

7. COLORAZIONI.

COLORAZIONI E NUMERO CROMATICO (PER VERTICI E PER LATI); STIME DEL NUMERO CROMATICO (ALGORITMO GOLOSO, TEOREMI DI BROOKS E DI VIZING). TEOREMA DEI 5 COLORI E CENNI SUL TEOREMA DEI 4 COLORI. OMOMORFISMI FRA GRAFI; HOM-EQUIVALENZA E CORE DI UN GRAFO.

8. TEORIA ALGEBRICA DEI GRAFI.

OPERATORI D'ADIACENZA, D'INCIDENZA ORIENTATA E LAPLACIANO DI UN GRAFO; SPAZIO DEI FLUSSI E SPAZIO DEI TAGLI; TEOREMA "MATRIX-TREE" DI KIRCHOFF.
Metodi Didattici
CIRCA DUE TERZI DELL'ATTIVITÀ FRONTALE SARANNO DEDICATI ALLE LEZIONI E CIRCA UN TERZO ALLE ESERCITAZIONI, IN CUI VERRANO PROPOSTI ESERCIZI E PROBLEMI RELATIVI AGLI ARGOMENTI DELLE LEZIONI: ALCUNI DI QUESTI ESERCIZI VERRANNO SVOLTI DAL DOCENTE IN AULA, MENTRE ALTRI SARANNO PROPOSTI COME HOMEWORK, IN MODO CHE LO STUDENTE POSSA SVILUPPARE LA PROPRIA CAPACITÀ DI RISOLVERE PROBLEMI IN MANIERA AUTONOMA.
Verifica dell'apprendimento
L'ESAME FINALE HA LO SCOPO DI VERIFICARE L'EFFETTIVO APPRENDIMENTO DEGLI ARGOMENTI DI TEORIA ESPOSTI A LEZIONE, NONCHÈ LA CAPACITÀ DEL CANDIDATO DI APPLICARE LA TEORIA ALLA RISOLUZIONE DI PROBLEMI CONCRETI. L'ESAME, CHE SI TERRÀ IN UN'UNICA SEDUTA, CONSISTERÀ IN:

1. LA DISCUSSIONE ORALE DI UNO DEGLI HOMEWORK PROPOSTI DURANTE IL CORSO, A SCELTA DELL'ESAMINATORE;

2. LO SVOLGIMENTO SCRITTO DI UN SEMPLICE ESERCIZIO, SU UN ARGOMENTO DIVERSO DA QUELLO DELL'HOMEWORK DI CUI AL PUNTO 1

3. UN COLLOQUIO ORALE SU ARGOMENTI DEL PROGRAMMA A SCELTA DELL'ESAMINATORE.
Testi
T. HARJU, GRAPH THEORY, LECTURE NOTES (2012, REPERIBILI SU INTERNET)

B. BOLLOBAS: MODERN GRAPH THEORY (GTM 184, SPRINGER, 1998)

C. GODSIL, G.F. ROYLE: ALGEBRAIC GRAPH THEORY (GTM 207, SPRINGER, 2001)

APPUNTI DEL DOCENTE


TESTI DI APPROFONDIMENTO:

J.A. BONDY, U.S.R. MURTY, GRAPH THEORY (GTM SPRINGER, 2008)

R. DIESTEL: GRAPH THEORY (GTM SPRINGER, 2006)

N. BIGGS: ALGEBRAIC GRAPH THEORY (CAMBRIDGE UNIVERSITY PRESS, 1993)

D. WEST, INTRODUCTION TO GRAPH THEORY, PRENTICE HALL 2001

Altre Informazioni
NESSUNA
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2022-05-23]