2. Docenti
  3. PUGLIESE Fabrizio
  4. Didattica

TEORIA DEI GRAFI

Fabrizio PUGLIESE TEORIA DEI GRAFI

0512300028
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2023/2024

ANNO CORSO 3
ANNO ORDINAMENTO 2018
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
FABRIZIO PUGLIESE T Curriculum
Obiettivi
L’INSEGNAMENTO HA L’OBIETTIVO PRIMARIO DI IMPARTIRE LE NOZIONI FONDAMENTALI DI TEORIA DEI GRAFI, TANTO NEI SUOI ASPETTI TEORICI QUANTO IN QUELLI APPLICATIVI.

- CONOSCENZA E CAPACITA' DI COMPRENSIONE: SCOPO DELL’INSEGNAMENTO È FORNIRE LE CONOSCENZE DI BASE DI TEORIA DEI GRAFI. LO STUDENTE AVRÀ MODO DI VEDERE COME
DA UNA NOZIONE ASSAI SEMPLICE COME QUELLA DI GRAFO SI SIA SVILUPPATA UNA TEORIA ESTREMAMENTE RICCA DI RISULTATI DI TIPO TOPOLOGICO (IMMERGIBILITÀ DI GRAFI IN SUPERFICI, COLORABILITÀ, CONNETTIVITÀ), ALGEBRICO (TEORIA SPETTRALE DEI GRAFI, MORFISMI FRA GRAFI) E COMBINATORIO. INOLTRE, SI ESPORRANO ALCUNE APPLICAZIONI FONDAMENTALI DEI GRAFI, IN PARTICOLARE A VARI PROBLEMI D'OTTIMIZZAZIONE (ALGORITMI DI DIJKSTRA, KRUSKAL, FORD-FULKERSON, PROBLEMI DI MATCHING, ECC.)

- CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE: SI VUOL METTERE LO STUDENTE IN GRADO DI APPLICARE CONCRETAMENTE LE NOZIONI TEORICHE APPRESE; A TALE SCOPO VERRÀ DATO AMPIO SPAZIO ALLE ESERCITAZIONI (CIRCA 1/3 DEL TOTALE DELLE ORE). OLTRE AGLI ESERCIZI SVOLTI IN AULA, VERRANNO ASSEGNATI ANCHE ESERCIZI DA RISOLVERE AUTONOMAMENTE COME HOMEWORK.
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. 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-12-17]