2. Docenti
  3. Didattica

TEORIA DEI GRAFI

Fabrizio PUGLIESE TEORIA DEI GRAFI

0512300028
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2014/2015

ANNO CORSO 3
ANNO ORDINAMENTO 2010
PRIMO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
FABRIZIO PUGLIESE T Curriculum
Obiettivi
- CONOSCENZA E CAPACITÀ DI COMPRENSIONE: SCOPO DEL CORSO È QUELLO DI FORNIRE ALCUNE CONOSCENZE DI BASE DELLA TEORIA DEI GRAFI, DI EVIDENZIARNE I LEGAMI CON ALTRI CAMPI DELLA MATEMATICA E DI MOSTRARNE ALCUNE DELLE INNUMEREVOLI APPLICAZIONI PRATICHE. LO STUDIO DEI GRAFI SARÀ L'OCCASIONE, PER LO STUDENTE DI: APPRENDERE ALCUNE TECNICHE FONDAMENTALI DI CALCOLO COMBINATORIO CHE NON VENGONO SOLITAMENTE IMPARTITE NEI CORSI OBBLIGATORI DELLA LAUREA TRIENNALE; VEDERE ALCUNE SORPRENDENTI APPLICAZIONI DELL'ALGEBRA LINEARE ALLO STUDIO DELLA STRUTTURA DI UN GRAFO; RENDERSI CONTO DELL'IMMENSO CAMPO D'AZIONE DELLA TEORIA DEI GRAFI E DI COME ESSA PERVADA QUASI TUTTI I SETTORI DELLA MATEMATICA APPLICATA. NONOSTANTE GLI OVVI LIMITI IMPOSTI DAL TEMPO A DISPOSIZIONE E DALLE LIMITATE CONOSCENZE PRELIMINARI DEGLI STUDENTI, SI È CERCATO DI DARE UN QUADRO ORGANICO E UNA VISIONE D'INSIEME RAGIONEVOLMENTE COMPLETA DELL'ARGOMENTO, PUNTANDO SOPRATTUTTO A METTERE IN EVIDENZA QUELLE CHE (A GIUDIZIO DEL DOCENTE) SONO LE LINEE FONDAMENTALI E I CONCETTI UNIFICANTI DELLA TEORIA.

- 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.).

- AUTONOMIA DI GIUDIZIO: FRA GLI OBIETTIVI PRINCIPALI DEL CORSO C'È QUELLO DI RENDERE LO STUDENTE QUANTO PIÙ POSSIBILE AUTONOMO E DI AIUTARLO A SVILUPPARE IL SUO SENSO CRITICO E LA CAPACITÀ DI INDIVIDUARE DA SÈ QUALI SIANO LE IDEE IMPORTANTI E GLI ARGOMENTI CHE POTREBBE VALERE LA PENA DI APPROFONDIRE IN STUDI SUCCESSIVI. A QUESTO SCOPO, NELLE ESERCITAZIONI, VERRANNO PROPOSTI, OLTRE A ESERCIZI STANDARD, ANCHE ALCUNI ARGOMENTI DI TEORIA DA SVOLGERE SOTTO FORMA DI PROBLEMI.

- ABILITÀ COMUNICATIVE: NEL CORSO VENGONO FORNITI ALLO STUDENTE GLI STRUMENTI LINGUISTICO/MATEMATICI ATTI A CONSENTIRGLI DI COMUNICARE CON SEMPLICITÀ E PRECISIONE ARGOMENTI DI TEORIA DEI GRAFI

- CAPACITÀ DI APPRENDIMENTO: TRA GLI SCOPI DEL CORSO C'È QUELLO DI AFFINARE LE FACOLTÀ ANALITICHE DELLO STUDENTE, LA SUA FLESSIBILITÀ MENTALE NELL'AFFRONTARE PROBLEMI PRATICI APPARENTEMENTE DIVERSI FRA LORO, MA CHE IN REALTÀ POSSONO ESSSERE RISOLTI CON LE STESSE TECNICHE DI TEORIA DEI GRAFI. A VOLTE, I DETTAGLI DI ALCUNE DIMOSTRAZIONI VERRANNO LASCIATI ALLO STUDENTE, IN PARTICOLARE IN QUEI CASI IN CUI ESSI RICALCANO PROCEDIMENTI GIÀ VISTI IN DIMOSTRAZIONI PRECEDENTI; SI CERCHERÀ, IN TAL MODO, DI SPINGERE LO STUDENTE AD ABBANDONARE QUELL'ATTEGGIAMENTO PASSIVO NELL'APPRENDIMENTO, CHE È SPESSO IL PRINCIPALE OSTACOLO ALLA MATURAZIONE SCIENTIFICA E CULTURALE DELLO STUDENTE.
Prerequisiti
I PREREQUISITI NECESSARI 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: 2016-09-30]