2. Docenti
  3. Didattica

TEORIA DEI GRAFI

Fabrizio PUGLIESE TEORIA DEI GRAFI

0512300028
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2024/2025

ANNO CORSO 3
ANNO ORDINAMENTO 2018
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
FABRIZIO PUGLIESE T Curriculum
AppelloData
TEORIA DEI GRAFI07/01/2025 - 09:00
TEORIA DEI GRAFI27/01/2025 - 09:00
TEORIA DEI GRAFI17/02/2025 - 09:00
Obiettivi
L'INSEGNAMENTO HA L'OBIETTIVO PRIMARIO DI IMPARTIRE LE NOZIONI FONDAMENTALI DI TEORIA DEI GRAFI.


- 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.
NON SONO PREVISTE PROPEDEUTICITÀ
Contenuti
IL CORSO CONSISTE DI UN UNICO MODULO, PER UN TOTALE DI 48 ORE DI DIDATTICA FRONTALE. RIPORTIAMO DI SEGUITO IL PROGRAMMA DETTAGLIATO, CON L'INDICAZIONE DEL NUMERO DI ORE PREVISTE PER CIASCUN ARGOMENTO.


1. NOZIONI DI BASE. (3 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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À. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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. MATCHING. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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. (5 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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


7. COLORAZIONI. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


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. (4 ORE DI LEZIONI + 2 DI ESERCITAZIONI)


OPERATORI D'ADIACENZA, D'INCIDENZA ORIENTATA E LAPLACIANO DI UN GRAFO; PROPRIETÀ SPETTRALI DI UN GRAFO; SPAZIO DEI FLUSSI E SPAZIO DEI TAGLI; TEOREMA "MATRIX-TREE" DI KIRCHOFF.
Metodi Didattici
IL CORSO SI ARTICOLA IN LEZIONI FRONTALI (CIRCA 32 ORE) ED ESERCITAZIONI (CIRCA 16 ORE). LE LEZIONI FRONTALI CONSENTIRANNO ALLO STUDENTE DI ACQUISIRE LE NOZIONI TEORICHE DI TEORIA DEI GRAFI ELENCATE NELLA SEZIONE "CONTENUTI DEL CORSO". LE ESERCITAZIONI MOSTRERANNO ALLO STUDENTE COME LE NOZIONI TEORICHE APPRESE SI APPLICHINO AD ESEMPI CONCRETI; INOLTRE, LA DIMOSTRAZIONE DI ALCUNI TEOREMI VERRÀ PROPOSTA SOTTO FORMA DI SERIE DI ESERCIZI, LA CUI RISOLUZIONE PORTERÀ GRADUALMENTE LO STUDENTE AL RISULTATO TEORICO FINALE. PARTE DEGLI ESERCIZI VERRÀ SVOLTA 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 CONSISTE IN UNA PROVA ORALE, DELLA DURATA DI CIRCA 45 MINUTI. LO STUDENTE DOVRÀ RISPONDERE A DUE DOMANDE DI TEORIA E DISCUTERE UNO DEGLI ESERCIZI SVOLTI IN AULA O ASSEGNATI COME HOMEWORK; IL VOTO FINALE SI OTTERRÀ DA UNA COMBINAZIONE PESATA DELLE RISPOSTE AI TRE QUESITI, CON UN PESO DEL 30% ASSEGNATO AI DUE QUESITI TEORICI E UN PESO DEL 40% ASSEGNATO ALLA DISCUSSIONE DELL'ESERCIZIO. LA VALUTAZIONE FINALE SARA' ESPRESSA IN TRENTESIMI. IL CONSEGUIMENTO DEL PUNTEGGIO MINIMO CORRISPONDE A UNA CONSCENZA BASILARE DEI CONTENUTI DEL CORSO. LA LODE POTRÀ ESSERE ATTRIBUITA AGLI STUDENTI CHE DIMOSTRINO DI ESSERE IN GRADO DI APPLICARE AUTONOMAMENTE CONOSCENZE E COMPETENZE ACQUISITE ANCHE IN CONTESTI DIVERSI DA QUELLI PROPOSTI A LEZIONE.
Testi
TESTI DI RIFERIMENTO:

- F.PUGLIESE: APPUNTI ED ESERCIZI SVOLTI SU ARGOMENTI DI TEORIA DEI GRAFI (REPERIBILI AL LINK HTTPS://DOCENTI.UNISA.IT/004411/RISORSE)

- T. HARJU, GRAPH THEORY, LECTURE NOTES (2012, REPERIBILI AL LINK HTTPS://USERS.UTU.FI/HARJU/GRAPHTHEORY/GRAPHTHEORY.PDF)

- C. GODSIL, G. ROYLE, ALGEBRAIC GRAPH THEORY (SPRINGER 2001)

TESTI DI CONSULTAZIONE E APPROFONDIMENTO:

- B. BOLLOBAS, MODERN GRAPH THEORY (SPRINGER 1998)

- D. WEST, INTRODUCTION TO GRAPH THEORY (PRENTICE HALL 1996)

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

- M. AIGNER, DISCRETE MATHEMATICS (AMERICAN MATHEMATICAL SOCIETY 2007)
Altre Informazioni
EMAIL: fpuglies@unisa.it
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-11-18]