Algebra combinatoria
A.A. 2020/2021
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
Le lezioni verranno erogate online, in modalità sincrona, attraverso la piattaforma Zoom o piattaforme simili.
Anche le prove d'esame, qualora non possibili in presenza, si svolgeranno attraverso la stessa piattaforma.
Anche le prove d'esame, qualora non possibili in presenza, si svolgeranno attraverso la stessa piattaforma.
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 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.
L'esame si intende superato se gli esercizi assegnati vengono svolti correttamente e se viene superata la prova orale. Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
L'esame si intende superato se gli esercizi assegnati vengono svolti correttamente e se viene superata la prova orale. Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
Docente/i
Ricevimento:
su appuntamento via e-mail
studio 1014, Via Saldini 50