1015531 - TEORIA DEI GRAFI
Risultati di apprendimento attesi
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à aquisiti. 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).
Modalità di svolgimento dell'insegnamento
Teoria dei Grafi 9 CFU
Organizzazione didattica
225 ore d'impegno totale
152 di studio individuale
49 di lezione frontale
24 di esercitazione
L’insegnamento verrà svolto mediante lezioni frontali in aula tenute dal docente. In tali lezioni il programma verrà suddiviso in: Introduzione storica e problematiche aperte nella teoria dei Grafi, nozioni di base, Parametri associati a grafi planari, Colorazioni dei vertici, numero cromatico, colorazioni degli spigoli, indice cromatico -
Polinomio cromatico e sue applicazioni - Classificazione dei grafi, grafi orientati, reti di flusso, grafi fortemente connessi.
In ognuna di tali sezioni il docente dapprima affronta i principali argomenti teorici e poi mostra come tali argomenti possono legarsi a possibili applicazioni. In seguito possono essere presentati algoritmi che permettono nella maggior parte dei casi di individuare particolari grafi o soluzioni proposte dai risultati teorici.
Una parte del programma (max 3CFU) potrà essere svolta da un professore straniero e/o italiano esperto di teoria dei grafi.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.
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. Filippo Stanco
Prerequisiti richiesti
Si richiedono alcune conoscenze di base contenute nell' insegnamento di Geometria 1.
Frequenza lezioni
Contenuti del corso
Grafi: introduzione storica, prime definizioni (grado, catena, connessione, …), teorema sui gradi dei vertici, grafi connessi, grafi bipartiti, grafi completi – Grafi euleriani e Grafi hamiltoniani: il problema dei ponti di
Konigsberg, caratterizzazione dei grafi euleriani, il problema del dodecaedro, il problema (aperto) della caratterizzazione dei grafi hamiltoniani – Alberi: definizioni, teoremi di caratterizzazione, albero di economia, applicazioni.
Grafi planari: definizioni e primi teoremi, il teorema di Eulero, grafi planari massimali, non planarità di K5 e K3,3, il teorema di Kuratowski.
Fattorizzazioni: accoppiamenti in un grafo – accoppiamenti completo – fattorizzazioni – fattorizzazione dei grafi completi e dei grafi bipartiti completi – il teorema di Hall e sue applicazioni (es: transversals, quadrati latini, matrici (0,1))
Colorazione dei vertici: colorazione dei vertici di un grafo, numero cromatico, numero di stabilità, teorema di Brooks, relazioni tra numero cromatico e numero di stabilità, relazioni tra il numero cromatico di un grafo e quello del suo complementare, teorema di Finck* – Colorazione dei grafi planari, teorema dei 5 colori, teorema dei 4 colori*, algoritmo di connessione e contrazione – Costruzione di Mycielski, densità cromatica.
Colorazione degli spigoli: colorazione degli spigoli di un grafo, indice cromatico, teorema di Konig, teorema di Vizing, il problema (aperto) della classificazione dei grafi, grafo di Petersen, grafi di Petersen generalizzati*.
Polinomio cromatico: definizioni, proprietà e teoremi, determinazione del polinomio cromatico, caratterizzazione degli alberi mediante il polinomio cromatico, polinomio cromatico dei cicli – Applicazioni
del polinomio cromatico: Disposizioni condizionate, disposizioni e colorazione dei vertici, Sudoku e polinomi cromatici.
Stabilità interna e stabilità esterna: definizioni e teoremi, numero di stabilità interna e numero di stabilità esterna, il problema delle 8 regine (Gauss), il problema del numero minimo di regine.
Grafi orientati. Reti di flusso. Algoritmo di Ford-Fulkerson. Grafi fortemente connessi, minimamente connessi, algoritmo di Tremaux, problema del cammino più breve, Cicli e cocicli, alberi e coalberi: numero ciclomatico e cociclomatico e richiami di l'algebra lineare, alberi e coalberi e loro proprietà. Applicazioni grafi orientati (es: Markov chains, matroidi)
Ipergrafi e G-designs: Concetti e definizioni principali.
Matroidi: concetti e definizioni principali
Testi di riferimento
- C. Berge, "Graph and Hypergraph", Elsevier.
- Appunti del docente
- M. Gionfriddo, Notes on Graph Theory 2018 (disponibili con il consenso del Prof. Emerito M. Gionfriddo)
- R. J. Wilson, Introduction to Graph Theory, Longman, 1996
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Grafi | 1,2,3 |
| 2 | Grafi Planari | 1,2,3 |
| 3 | Fattorizzazioni | 1,2,3 |
| 4 | Colorazioni di vertici | 1,2,3 |
| 5 | Colorazioni degli spigoli | 1,2,3 |
| 6 | Polinomio cromatico | 1,2,3 |
| 7 | Stabilità interna ed esterna | 1,2,3 |
| 8 | Grafi orientati | 1,2,3 |
| 9 | reti di flusso | 1,2,3 |
| 10 | Grafi fortemente connessi | 1,2,3 |
| 11 | cenni su Ipergrafi e G-Designs | 1,2,3 |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
a) Verifica durante il corso: Periodicamente, durante le lezioni, gli studenti saranno invitati a citare definizioni e risultati trattati nelle lezioni precedenti, per favorire un apprendimento consapevole della disciplina.
b) esame finale: l'esame finale consiste una prova orale alla fine del corso. La prova orale è mirata particolarmente a verificare la chiarezza espositiva e la capacità di collegare fra loro diversi argomenti del programma.
d) criteri per l’attribuzione del voto: si terrà conto: della chiarezza espositiva, della completezza delle conoscenze, della capacità di collegare diversi argomenti.
Per l'attribuzione del voto della prova finale 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.
NOTA BENE La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.
Esempi di domande e/o esercizi frequenti
- Grafi planari e loro proprietà.
- Alberi e loro caratterizzazione. Alberi di economia
- Grafi Euleriani ed Hamiltoniani.
- Il problema del percorso minimo.
- Teorema di Ford-Fulkerson.
- Teorema di Köenig-Hall.
- Teorema di Vizing.
- Colorazione dei vertici e degli spigoli
- Reti di flusso
- Grafi fortemente connessi
- Esempi ed applicazioni
English version