GRAPHS AND HYPERGRAPHS

Il corso avrà i seguenti obiettivi:

Conoscenza e capacità di comprensione:

- Comprensione degli strumenti matematici quali teoremi e algoritmi in teoria dei grafi che permettono di sviluppare abilità matematiche nel ragionamento e nel calcolo. Tali abilità dovrebbero permettere di risolvere problemi già conosciuti e trasformarli in modelli matematici.

Capacità di applicare conoscenza e comprensione:

- Alla fine del corso si dovrà acquisire una conoscenza utile al rigoroso utilizzo delle nuove tecniche matematiche e una comprensione degli argomenti trattati che renda possibile i collegamenti tra i vari argomenti già acquisiti. Lo studente dovrà essere posto in condizioni di proporre nuove problematiche che richiedono originalità di pensiero e tecniche di formalizzazione matematica utili alla risoluzione di tali problemi.

Autonomia di giudizio:

- Il corso, basato su un metodo logico deduttivo, darà allo studente capacità autonome di giudizio per discernere metodi di dimostrazioni non corrette inoltre, mediante un ragionamento logico, si dovranno affrontare adeguate problematiche di teoria dei grafi cercando di risolverle con l'aiuto interattivo del docente.

Abilità comunicative

- Nella prova finale di esame lo studente dovrà dimostrare di aver raggiunto una adeguata maturità espositiva delle varie tecniche matematiche apprese utilizzando anche strumenti multimediali.

Capacità di apprendimento:

- Alla fine del corso lo studente dovrà essere in grado di poter affrontare in autonomia argomenti teorici e applicativi che potranno essere incontrati in nuovi insegnamenti o in campi lavorativi; ad esempio la teoria dei flussi nei grafi e tutti i problemi di connettività hanno ampia applicazione nel campo delle telecomunicazioni (reti locali e reti metropolitane: LAN e MAN) e nei campi elettrico e delle comunicazioni (progettazione).

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 in presenza di studenti Erasmus

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.

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.

Esame orale con esposizione degli argomenti richiesti.

Per l'attribuzione del voto si seguiranno di norma i seguenti criteri:

non approvato: lo studente non ha acquisito i concetti di base e non è in grado di svolgere gli esercizi.

18-23: lo studente dimostra una padronanza minima dei concetti di base, le sue capacità di esposizione e di collegamento dei contenuti sono modeste, riesce a risolvere semplici esercizi.

24-27:  lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione e di collegamento dei contenuti sono buone,  risolve gli esercizi con pochi errori.

28-30 e lode: lo studente ha acquisito tutti i contenuti del corso ed è in grado di esporli compiutamente e di collegarli con spirito critico; risolve gli esercizi in modo completo e senza errori.

Qualora le condizioni lo dovessero richiedere, la verifica dell'apprendimento potrà essere effettuata anche per via telematica.

NOTA BENE: Informazioni per studenti con disabilità e/o DSA

A garanzia di pari opportunità e nel rispetto delle leggi vigenti, gli studenti interessati possono chiedere un colloquio personale in modo da programmare eventuali misure compensative e/o dispensative, in base agli obiettivi didattici ed alle specifiche esigenze.

E' possibile rivolgersi anche al docente referente CInAP (Centro per l'integrazione Attiva e Partecipata - Servizi per le Disabilità e/o i DSA) del nostro Dipartimento, prof.ssa Daniele

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"