2. Docenti
  3. PUGLIESE Fabrizio
  4. Didattica

TEORIA DEI GRAFI

Fabrizio PUGLIESE TEORIA DEI GRAFI

0512300028
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2016/2017

ANNO CORSO 3
ANNO ORDINAMENTO 2010
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] 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
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
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
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-03-11]