Grafi e Ipergrafi
Anno accademico 2026/2027 - Docente: Mario GIONFRIDDORisultati 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.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto sopra dichiarato, al fine di rispettare il programma previsto e riportato nel presente syllabus.
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.
Goal 4 Istruzione di Qualità – Assicurare un’istruzione inclusiva, equa e di qualità, e promuovere opportunità di apprendimento permanente.
Goal 5 Uguaglianza di Genere – Raggiungere l’uguaglianza di genere e l’autonomia di tutte le donne e ragazze.
Goal 6 Acqua Pulita e Servizi Igienico-Sanitari – Garantire la disponibilità e la gestione sostenibile dell’acqua e dei servizi igienico-sanitari per tutti.
Goal 8 Lavoro Dignitoso e Crescita Economica – Promuovere una crescita economica sostenuta, inclusiva e sostenibile, piena occupazione e lavoro dignitoso per tutti.
Goal 11 Città e Comunità Sostenibili – Rendere le città e gli insediamenti umani inclusivi, sicuri, resilienti e sostenibili.
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 | 1) C. Berge: ''Hypergraphs'', North-Holland (1989) 2) C.C.Lindner-C.Rodger: ''Design Theory'', CRC Boca Raton (2007)3) M.Gionfriddo, L.Milazzo, V.Voloshin: Hypergraphs and Designs, Nova Science, New York (2015) |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
Per partecipare all'esame finale è necessario avere effettuato la prenotazione sul portale SmartEdu. Per eventuali problemi tecnici relativi alla prenotazione occorre rivolgersi alla Segreteria didattica
Esame orale con esposizione degli argomenti richiesti.
La verifica dell'apprendimento potrà essere effettua
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"