Algebra combinatoria

A.A. 2019/2020
Insegnamento per
6
Crediti massimi
42
Ore totali
SSD
MAT/02
Lingua
Italiano
Obiettivi formativi
Il corso si propone di fornire i primi rudimenti di teoria dei grafi e delle sue applicazioni.
Conoscenza delle nozioni di base di teoria dei grafi e di alcune applicazioni.

Struttura insegnamento e programma

Edizione attiva
Responsabile
MAT/02 - ALGEBRA - CFU: 6
Lezioni: 42 ore
Docente: Montoli Andrea
Programma
Definizioni ed esempi, equivalenza tra grafi, grafi numerati, sottografi.
Grafi euleriani. Il problema dei sette ponti di Konigsberg e il problema del postino cinese.
Grafi Hamiltoniani. Il problema del commesso viaggiatore.
Tornei. Alberi: proprietà elementari, enumerazione di alberi.
Planarità e dualità.
Matrici associate ad un grafo, quadrati latini.
Matching. Teorema dei matrimoni di P. Hall, teorema di Menger e loro applicazioni.
Circuiti combinatorici.
Propedeuticità
Algebra 1 e 2.
Prerequisiti e modalità di esame
Durante il corso saranno assegnati degli esercizi, il cui svolgimento è condizione necessaria per sostenere la prova orale. L'esame si articola in una prova orale, che consiste in un colloquio sugli argomenti del programma, volto prevalentemente ad accertare la conoscenza degli argomenti teorici affrontati nel corso e delle loro applicazioni.
Metodi didattici
Lezioni frontali.
Materiale didattico e bibliografia
F. Harary, "Graph theory", 1969
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
su appuntamento via e-mail
studio 1026, Via Saldini 50