Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Ingegneria
ICT FOR INTERNET AND MULTIMEDIA - INGEGNERIA PER LE COMUNICAZIONI MULTIMEDIALI E INTERNET
Insegnamento
GRAPH THEORY - TEORIA DEI GRAFI
INP7080667, A.A. 2018/19

Informazioni valide per gli studenti immatricolati nell'A.A. 2018/19

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
ICT FOR INTERNET AND MULTIMEDIA - INGEGNERIA PER LE COMUNICAZIONI MULTIMEDIALI E INTERNET
IN2371, ordinamento 2017/18, A.A. 2018/19
N0
porta questa
pagina con te
Curriculum INTERNATIONAL MOBILITY [005PD]
Crediti formativi 6.0
Tipo di valutazione Voto
Denominazione inglese GRAPH THEORY
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Obbligo di frequenza No
Lingua di erogazione INGLESE
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile MICHELANGELO CONFORTI MAT/09

Mutuante
Codice Insegnamento Responsabile Corso di studio
SC04105572 MATEMATICA DISCRETA MICHELANGELO CONFORTI SC1159

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
AFFINE/INTEGRATIVA Attività formative affini o integrative MAT/09 6.0

Organizzazione dell'insegnamento
Periodo di erogazione Secondo semestre
Anno di corso I Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 6.0 48 102.0

Calendario
Inizio attività didattiche 25/02/2019
Fine attività didattiche 14/06/2019
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2019

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)
7 Matematica Discreta - a.a. 2018/2019 01/10/2018 30/09/2019 CONFORTI MICHELANGELO (Presidente)
DI SUMMA MARCO (Membro Effettivo)
DE FRANCESCO CARLA (Supplente)
DE GIOVANNI LUIGI (Supplente)
RINALDI FRANCESCO (Supplente)

Syllabus
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, --. Cerca nel catalogo
  • Bollobas, Bela, Modern graph theory. New York: Springer, --. Cerca nel catalogo

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Problem based learning
  • Case study
  • Problem solving

Didattica innovativa: Software o applicazioni utilizzati
  • Mathematica

Obiettivi Agenda 2030 per lo sviluppo sostenibile
Istruzione di qualita'