Dipartimento di DIPARTIMENTO DI MATEMATICA
Anno accademico 2016/2017
TEORIA DEI GRAFI [ 0512300028 ]
Nessun partizionamento Corso di studio MATEMATICA Ordinamento MATEMATICA
Percorso MATEMATICA AD INDIRIZZO APPLICATIVO Docenti: FABRIZIO PUGLIESE (Tit.)
Numero ore: 48
Periodo: PRIMO SEMESTRE Crediti: 6
Settori: MAT/03
Obiettivi formativi
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 del corso
[1] CENNI STORICI AI PROBLEMI DA CUI È NATA LA TEORIA DEI GRAFI |||
[2] NOZIONI DI BASE: VARI TIPI DI GRAFI (ORIENTATI E NON, MULTIPLI E SEMPLICI, PESATI); MORFISMI FRA GRAFI; SOTTOGRAFI; OPERAZIONI SUI GRAFI. |||
[3] CAMMINI, PASSEGGIATE, CICLI E NOZIONI ASSOCIATE (DISTANZA FRA VERTICI, DIAMETRO, CIRCONFERENZA, GIRTH, CENTRO, RAGGIO). |||
[4] ALBERI E FORESTE: VARIE CARATTERIZZAZIONI DEGLI ALBERI, ALBERI GENERATORI DI UN GRAFO, ALBERI NORMALI, ALGORITMI DI RICERCA IN UN GRAFO (DEPTH-FIRST, BREADTH-FIRST). |||
[5] GRAFI EULERIANI ED HAMILTONIANI:CARATTERIZZAZIONI DEI CIRCUITI EULERIANI E ALGORITMI PER DETERMINARLI; CICLI HAMILTONIANI; ALCUNI CRITERI DI HAMILTONICITÀ (GRAFI TOUGH, TEOREMA DI DIRAC). |||
[6] MATCHING E RICOPRIMENTI: GRAFI BIPARTITI, LORO CARATTERIZZAZIONE TRAMITE LA PARITÀ DEI CICLI; MATCHING E RICOPRIMENTI; MATCHING IN UN GRAFO BIPARTITO, TEOREMI DI HALL E DI KOENIG. |||
[7] CONNETTIVITÀ: GRAFI CONNESSI E K-CONNESSI; CONNETTIVITÀ PER VERTICI E PER LATI;
DISEGUAGLIANZE DI WHITNEY; TEOREMA DI MENGER; DECOMPOSIZIONE DI UN GRAFO IN BLOCCHI. ||| [8] TEORIA ALGEBRICA DEI GRAFI: SPAZI VETTORIALI ASSOCIATI A UN GRAFO, OPERATORI
D'ADIACENZA E DI INCIDENZA, SPETTRO DI UN GRAFO E SUE APPLICAZIONI (RELAZIONE FRA NUMERO DI AUTOVALORI E DIAMETRO DEL GRAFO, AUTOVALORI DI UN GRAFO LINEARE, ALGORITMI DEL TIPO PAGERANK PER MOTORI DI RICERCA; SPETTRO DI UN SOTTOGRAFO, SPETTRO DI UN GRAFO
REGOLARE), OPERATORI LAPLACIANO E DI COBORDO; SPAZIO DEI CICLI E SPAZIO DEI TAGLI; ALCUNI COMPLEMENTI DI ALGEBRA LINEARE (AGGIUNTO DI UN OPERATORE FRA SPAZI EUCLIDEI; AGGIUNTO CLASSICO DI UNA MATRICE; FORMULA DI CAUCHY-BINET); TEOREMA DI KIRCHOFF E FORMULA DI CAYLEY; FORMULE VARIE PER IL CALCOLO DEL NUMERO DI PASSEGGIATE, CAMMINI E CICLI DI LUNGHEZZA DATA IN UN GRAFO; APPLICAZIONE DELLA TEORIA DEI GRAFI ALL'ANALISI DELLE RETI ELETTRICHE. |||
[9] GRAFI PLANARI: FORMULA DI EULERO E SUE PRIME CONSEGUENZE, POLIEDRI REGOLARI, TEOREMA DI KURATOWSKI; DUALE DI UN GRAFO, CRITERIO DI PLANARITÀ DI WHITNEY; GRAFI IMMERGIBILI IN SUPERFICI, TEOREMA DI HEAWOOD. |||
[10] COLORAZIONI: COLORAZIONI PER VERTICI E PER LATI; K-COLORABILITÀ; NUMERO CROMATICO; COLORAZIONI DI GRAFI PIANI, TEOREMI DEI 5 COLORI E DEI 4 COLORI (CON LA "PROVA" DI KEMPE); STIMA DEL NUMERO CROMATICO TRAMITE L'ALGORITMO GREEDY E IL TEOREMA DI BROOKS; NUMERO DI K-COLORAZIONI, POLINOMIO CROMATICO. |||
[11] RETI E FLUSSI: TEOREMA "MAX-FLOW MIN-CUT" E NUOVA DEDUZIONE A PARTIRE DA ESSO DEI TEOREMI DI MENGER E DI HALL (V PUNTI [6],[7])
Metodi didattici
LEZIONI FRONTALI
Modalità di verifica dell'apprendimento
L'ESAME FINALE CONSISTERÀ IN: 1) UNA PROVA ORALE TRADIZIONALE SULLA PARTE DEL PROGRAMMA COMPRESA NEI PUNTI [2]-[11], VOLTA A VERIFICARE L'EFFETTIVA ASSIMILAZIONE, DA PARTE DEL CANDIDATO, DELLE NOZIONI TEORICHE; 2) LO SVOLGIMENTO DI QUALCHE SEMPLICE ESERCIZIO PER TESTARE LA CAPACITÀ DEL CANDIDATO DI APPLICARE CONCRETAMENTE LA TEORIA. A QUESTO RIGUARDO, DURANTE TUTTO IL CORSO VERRANNO ASSEGNATI AGLI STUDENTI DEI SEMPLICI ESERCIZI DI AUTOVERIFICA DA SVOLGERE A CASA; INOLTRE, DURANTE LE ESERCITAZIONI IN AULA GLI STUDENTI VERRANO SPESSO CHIAMATI ALLA LAVAGNA PER PROVARE A SVOLGERE, CON L'AIUTO DEL DOCENTE, GLI ESERCIZI PROPOSTI.
Testi di riferimento
R. DIESTEL: GRAPH THEORY (GTM SPRINGER, 2006)
B. BOLLOBAS: MODERN GRAPH THEORY (GTM 184, SPRINGER, 1998)
N. BIGGS: ALGEBRAIC GRAPH THEORY (CAMBRIDGE UNIVERSITY PRESS, 1993) C. GODSIL, G.F. ROYLE: ALGEBRAIC GRAPH THEORY (GTM 207, SPRINGER, 2001)
Altre informazioni
NESSUNA
Stampa del 20/09/2017
