|
Insegnamento
MATEMATICA DISCRETA
SC04105572, A.A. 2019/20
Informazioni valide per gli studenti immatricolati nell'A.A. 2017/18
Dettaglio crediti formativi
Tipologia |
Ambito Disciplinare |
Settore Scientifico-Disciplinare |
Crediti |
CARATTERIZZANTE |
Formazione Modellistico-Applicativa |
MAT/09 |
6.0 |
Organizzazione dell'insegnamento
Periodo di erogazione |
Secondo semestre |
Anno di corso |
III Anno |
Modalità di erogazione |
frontale |
Tipo ore |
Crediti |
Ore di didattica assistita |
Ore Studio Individuale |
ESERCITAZIONE |
3.0 |
24 |
51.0 |
LEZIONE |
3.0 |
24 |
51.0 |
Inizio attività didattiche |
02/03/2020 |
Fine attività didattiche |
12/06/2020 |
Visualizza il calendario delle lezioni |
Lezioni 2019/20 Ord.2008
|
Commissioni d'esame
Commissione |
Dal |
Al |
Membri |
8 Matematica Discreta - a.a. 2019/2020 |
01/10/2019 |
30/09/2020 |
CONFORTI
MICHELANGELO
(Presidente)
DI SUMMA
MARCO
(Membro Effettivo)
DE FRANCESCO
CARLA
(Supplente)
DE GIOVANNI
LUIGI
(Supplente)
RINALDI
FRANCESCO
(Supplente)
|
Prerequisiti:
|
concetti di base di matematica (tecniche di dimostrazione, combinatorica di base) |
Conoscenze e abilita' da acquisire:
|
Conoscenza dei risultati di base della teoria dei grafi. Capacita' di elaborazione autonoma di metodi di dimostrazione propri della matematica discreta. |
Modalita' di esame:
|
L'esame e' scritto. |
Criteri di valutazione:
|
Conoscenza del materiale presentato in classe. Abilita' nel dimostrare autonomamente fatti elementari della teoria dei grafi. |
Contenuti:
|
Grafi nonorientati: Definizioni di base, percorsi, cammini, tagli, connettivita'.
Alberi: Definizioni, proprieta' di base, cicli fondamentali, albero di peso minimo: Algoritmo di Kruskal.
Matchings nei grafi bipartiti: Definizioni, cammini alternanti ed aumentanti, teorema di Hall, teorema di Konig, matchings stabili.
Matchings nei grafi non-bipartiti: Teorema di Tutte, formula di Berge, identita' di Gallai.
Grafi orientati: Definizioni di base, percorsi e cammini orientati, cicli orientati, tagli, connettivita' forte. Grafi aciclici, tornei, cammini e cicli Hamiltoniani in tornei. Teorema di Gallai-Milgram, grafi di comparabilita'
Connettivita': connettivita' sui vertici ed archi, 3 teoremi di Menger, scomposizione ad orecchie.
Colorazione sui grafi: Numero cromatico ed arcocromatico, teorema di Vizing.
Planarita': Rappresentazioni piane e grafi duali, formula di Eulero, Teorema di Kuratowski, teorema di Tait.
Traversabilita': Grafi Hamiltoniani ed Euleriani. |
Attivita' di apprendimento previste e metodologie di insegnamento:
|
24 lezioni di 2 ore ciscuna. |
Eventuali indicazioni sui materiali di studio:
|
Informazioni dettagliate
sono riportate nel sito
https://sites.google.com/view/micheleconforti/teaching |
Testi di riferimento: |
-
Bondy, John Adrian; Murty, U. S. R., Graph theory. New York: Springer, --.
-
Bollobas, Bela, Modern graph theory. New York: Springer, --.
|
|
|