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
INP9087848, A.A. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2019/20

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
ICT FOR INTERNET AND MULTIMEDIA - INGEGNERIA PER LE COMUNICAZIONI MULTIMEDIALI E INTERNET (Ord. 2019)
IN2371, ordinamento 2019/20, A.A. 2019/20
N0
porta questa
pagina con te
Curriculum CYBERSYSTEMS [002PD]
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
ESERCITAZIONE 3.0 24 51.0
LEZIONE 3.0 24 51.0

Calendario
Inizio attività didattiche 02/03/2020
Fine attività didattiche 12/06/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2019

Commissioni d'esame
Nessuna commissione d'esame definita

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