GRAPHS AND HYPERGRAPHS
Anno accademico 2022/2023 - Docente: ELENA MARIA GUARDORisultati di apprendimento attesi
Modalità di svolgimento dell'insegnamento
Lezioni frontali in cui vengono svolti gli argomenti previsti dal programma, con segnalazioni di problematiche aperte e ancora irrisolte con l'intenzione di stimolare gli studenti verso lo studio e la risoluzione dei problemi.
E' possibile, su richiesta, effettuare le lezioni in lingua inglese.
Al fine di rispettare il programma previsto e riportato nel syllabus, qualora l'insegnamento dovesse essere effettuato in modalità "mista" o a "distanza", potranno essere introdotte le necessari variazioni rispetto a quanto descritto in precedenza.
Prerequisiti richiesti
Frequenza lezioni
Contenuti del corso
Teoria dei Grafi: Concetti introduttivi della teoria dei grafi, planarità, connessione, strutture particolari - Origine e sviluppo storico delle moderne teorie combinatorie - Colorazione dei vertici, colorazione degli spigoli - Problematiche aperte e temi di iricerca - Relazioni tra numero cromatico e altri parametri - Algoritmi - Polinomio cromatico e applicazioni - Classificazione dei grafi - Problemi aperti.
Teoria degli Ipergrafi: Ipergrafi, concetti e parametri associati agli ipergrafi - Sistemi di Steiner, STS, SQS, S(2,4,v), caratterizzazione, blocking sets, costruzioni, parallelismo, metodo delle differenze - G-designs, G-desings bilanciati e fortemente bilanciati, casi vari di costruzione dei G-designs (graph-designs), metodo delle differenze per i G-designs - H-designs (hypergraph-designs), costruzione di H-designs, metodo della matrice delle differenze.
Problemi aperti e Congetture storiche della teoria dei Grafi e degli Ipergrafi. Risultati noti.
Testi di riferimento
1) C. Berge: ''Hypergraphs'', North-Holland (1989) | |
2) C.C.Lindner-C.Rodger: ''Design Theory'', CRC Boca Raton (2007)
|
Programmazione del corso
Argomenti | Riferimenti testi | |
---|---|---|
1 | Grafi - Ipergrafi - Sistemi d Steiner - H-designs |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
Esame orale con esposizione degli argomenti richiesti.
Qualora le condizioni lo dovessero richiedere, la verifica dell'apprendimento potrà essere effettuata anche per via telematica.
Esempi di domande e/o esercizi frequenti
1) Costruzione di Bose per i Sistemi di Terne di Steiner
2) Determinazione dello spettro dei G-designs bilanciati
3) Teorema sui blocking sets per i Sistemi di Quaterne di Steiner
4) Il problema della "classificazione dei grafi"
5) Costruzione di Sistemi S(2,k,v) con il "metodo delle differenze"