Presentazione

Organizzazione della Didattica

DM270
MATEMATICA

Matematica discreta

6

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 24 24 0 150

Periodo

AnnoPeriodo
III anno2 semestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Inglese

Calendario Attività Didattiche

InizioFine
02/03/202012/06/2020

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteFormazione modellistico-applicativaMAT/096


Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. CONFORTI MICHELANGELOMAT/09Dipartimento di Matematica

Altri Docenti

Non previsti

Attività di Supporto alla Didattica

Non previste

Bollettino

concetti di base di matematica (tecniche di dimostrazione, combinatorica di base)

Conoscenza dei risultati di base della teoria dei grafi. Capacita' di elaborazione autonoma di metodi di dimostrazione propri della matematica discreta.

24 lezioni di 2 ore ciscuna.

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.

L'esame e' scritto.

Conoscenza del materiale presentato in classe. Abilita' nel dimostrare autonomamente fatti elementari della teoria dei grafi.

Bondy, John Adrian; Murty, U. S. R., Graph theory. New York: Springer, 0 Bollobas, Bela, Modern graph theory. New York: Springer, 0

Informazioni dettagliate sono riportate nel sito https://sites.google.com/view/micheleconforti/teaching

concetti di base di matematica (tecniche di dimostrazione, combinatorica di base)

Conoscenza dei risultati di base della teoria dei grafi. Capacita' di elaborazione autonoma di metodi di dimostrazione propri della matematica discreta.

24 lezioni di 2 ore ciscuna.

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.

L'esame e' scritto.

Conoscenza del materiale presentato in classe. Abilita' nel dimostrare autonomamente fatti elementari della teoria dei grafi.

Bondy, John Adrian; Murty, U. S. R., Graph theory. New York: Springer, 0 Bollobas, Bela, Modern graph theory. New York: Springer, 0

Informazioni dettagliate sono riportate nel sito https://sites.google.com/view/micheleconforti/teaching