Algebra combinatoria
A.A. 2023/2024
Obiettivi formativi
L'insegnamento si propone di fornire i primi rudimenti di teoria dei grafi e delle sue applicazioni.
Risultati apprendimento attesi
Conoscenza delle nozioni di base di teoria dei grafi e di alcune applicazioni.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
Definizioni ed esempi di grafi, isomorfismi tra grafi, sottografi, invarianti per grafi.
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 colorazioni di grafi.
Reti e flussi.
Matching. Teorema dei matrimoni di Hall, teorema di Menger e loro applicazioni.
Quadrati latini e legame con le strutture algebriche.
Circuiti combinatorici.
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 colorazioni di grafi.
Reti e flussi.
Matching. Teorema dei matrimoni di Hall, teorema di Menger e loro applicazioni.
Quadrati latini e legame con le strutture algebriche.
Circuiti combinatorici.
Prerequisiti
Conoscenze elementari di teoria degli insiemi e di teoria dei gruppi.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
F. Harary, "Graph theory", 1969
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
Modalità di verifica dell’apprendimento e criteri di valutazione
Durante il corso saranno assegnati degli esercizi, che saranno pubblicati sulla pagina dell'insegnamento nel portale Ariel. Lo svolgimento degli esercizi assegnati è condizione necessaria per sostenere la prova orale. L'esame si articola una prova orale, che consiste in un colloquio sugli argomenti del programma dell'insegnamento, volto prevalentemente ad accertare la conoscenza degli argomenti teorici affrontati nel corso e delle loro applicazioni.
Siti didattici
Docente/i
Ricevimento:
su appuntamento via e-mail
studio 1014, Via Saldini 50