9795991 - GRAPHS AND HYPERGRAPHS
Risultati di apprendimento attesi
L'insegnamento si propone di far acquisire agli studenti i metodi e le tecniche più moderne, nell'ambito delle teorie combinatorie più recenti. Scopo del corso è anche fornire conoscenze sui temi di ricerca attualmente più studiati nell'ambito della teoria dei grafi, degli ipergrafi e dei block-designs. Nell'ambito del corso vengono affrontate molteplici problematiche di Matematica Discreta. Di tutti i temi studiati si danno ampi orientamenti di carattere applicativo.
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
Concetti introduttivi e nozioni elementari di matematica combinatoria e teoria dei grafi.
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 |
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.
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"
English version