Teoria dei Grafi
Anno accademico 2026/2027 - Docente: ELENA MARIA GUARDORisultati 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
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.
Agli studenti del corso di laurea triennale/magistrale in Informatica verrà distribuito un programma dettagliato perchè l'insegnamento vale 6 cfu e pertanto agli esami verranno omesse alcune dimostrazioni.
Per partecipare all'esame finale è necessario avere effettuato la prenotazione sul portale SmartEd
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
Per una comprensione approfondita degli argomenti trattati e delle metodologie presentate, si raccomanda vivamente la regolare partecipazione alle lezioni.
Contenuti del corso
Grafi: introduzione storica, il problema dei ponti di Konigsberg, prime definizioni (grado, catena, connessione, …), teorema sui gradi dei vertici, grafi connessi, grafi bipartiti, grafi completi – Grafi euleriani e loro caratterizzazione (dimostrazione) e Grafi hamiltoniani, teorema di Ore, Dirac (dimostrazione) e di Bondy-Chvatal (solo enunciato), il problema del dodecaedro, il problema (aperto) della caratterizzazione dei grafi hamiltoniani – Alberi (dimostrazioni su tutto il capitolo): definizioni, teoremi di caratterizzazione, albero di economia, minimum spanning tree (MST) ed applicazioni.
Grafi planari: definizioni e primi teoremi, il teorema di Eulero (dimostrazione), grafi planari massimali, non planarità di K5 e K3,3, il teorema di Kuratowski (solo enunciato).
Fattorizzazioni: accoppiamenti in un grafo – accoppiamenti completo – fattorizzazioni – fattorizzazione dei grafi completi e dei grafi bipartiti completi – il teorema di Hall (dimostrazione opzionale) e sue applicazioni con esempi: transversals, quadrati latini, matrici (0,1)
Colorazione dei vertici: colorazione dei vertici di un grafo, numero cromatico, numero di stabilità, teorema di Brooks (solo enunciato), relazioni tra numero cromatico e numero di stabilità, relazioni tra il numero cromatico di un grafo e quello del suo complementare, teorema di Finck (no dimostrazione) – Colorazione dei grafi planari, teorema dei 5 colori (dimostrazione), teorema dei 4 colori (solo enunciato), algoritmo di connessione e contrazione con esempi – Costruzione di Mycielski, densità cromatica.
Colorazione degli spigoli: colorazione degli spigoli di un grafo, indice cromatico, teorema di Konig (dimostrazione), teorema di Vizing (no dimostrazione), il problema (aperto) della classificazione dei grafi, grafo di Petersen, grafi di Petersen generalizzati (solo enunciati).
Polinomio cromatico: definizioni, proprietà e teoremi (dimostrazione), 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. Esempi.
Grafi orientati. Reti di flusso. Algoritmo di Ford-Fulkerson e teorema di Ford-Fulkerson (dimostrazione). Grafi fortemente connessi e loro caratterizzazione (dimostrazione), minimamente connessi, algoritmo di Tremaux (dimostrazione), problema del cammino più breve, Cicli e cocicli, alberi e coalberi: numero ciclomatico e cociclomatico (richiami di l'algebra lineare), alberi e coalberi e loro proprietà. Applicazioni grafi orientati (es: Markov chains, matroidi)
Matroidi: Concetti e definizioni principali.
Modalità:
Goal 5 Uguaglianza di Genere – Raggiungere l’uguaglianza di genere e l’autonomia di tutte le donne e ragazze.
Goal 8 Lavoro Dignitoso e Crescita Economica – Promuovere una crescita economica sostenuta, inclusiva e sostenibile, piena occupazione e lavoro dignitoso per tutti.
La teoria dei grafi aiuta a comprendere, ottimizzare e rendere più equi i sistemi economici e lavorativi. Favorisce innovazione, inclusione e sostenibilità, tre pilastri fondamentali del Goal 8. È uno strumento matematico e computazionale con forti ricadute sociali e politiche.
Goal 11: Città e Comunità Sostenibili – Rendere le città e gli insediamenti umani inclusivi, sicuri, resilienti e sostenibili.
Il Goal 11 dell’Agenda 2030 — “Città e comunità sostenibili” — ha una connessione molto profonda con la teoria dei grafi, perché le città sono, in pratica, reti complesse di collegamenti: strade, trasporti, reti energetiche, flussi informativi, sociali e ambientali.
Esempi pratici di collegamenti con i goals
Analisi delle reti di impresa per individuare opportunità di crescita locale.
Studio delle reti di collaborazione scientifica per sviluppare settori ad alta innovazione.
Ottimizzazione delle reti di trasporto e distribuzione per ridurre sprechi e creare lavoro.
Modellazione del mercato del lavoro per rendere l’occupazione più efficiente e accessibile.
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
Testi di riferimento
- C. Berge, "Graph and Hypergraph", Elsevier.
- Appunti del docente forniti su MS TEAMS
- 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
- Cormen Solo per la parte delle reti di flusso
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Grafi | 1),2),3) |
| 2 | Alberi e loro caratterizzazioni | 2) 3) 4) |
| 3 | Grafi Euleriani ed Hamiltoniani | 2) 3) 4) |
| 4 | Grafi planari | 2) 3) |
| 5 | Fattorizzazioni | 2) 3) |
| 6 | Colorazione vertici | 1) |
| 7 | Colorazione degli spigoli | 1) |
| 8 | Polinomio cromatico | 1) 2) 3) 4) |
| 9 | Stabilità interna ed esterna | 2) 3) |
| 10 | Grafi orientati | 1) 2) 3) |
| 11 | Reti di flusso | 1) 2) 5) |
| 12 | Grafi fortemente connessi | 3) 4) |
| 13 | Matroidi | 4) |
| 14 | cenni su G designs e Hypergraphs | 1) 3) |
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.
La prova d’esame è finalizzata a valutare in modo approfondito la preparazione dello studente, la capacità di analisi e di ragionamento sugli argomenti trattati durante il corso, nonché l’adeguatezza del linguaggio tecnico utilizzato.
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 esempi.
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 fare semplici esempi.
24-27: lo studente dimostra una buona padronanza dei contenuti del corso, le sue capacità di esposizione e di collegamento dei contenuti sono buone.
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; riesce a fare gli esempi.
La verifica dell'apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere. 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. È possibile rivolgersi anche al docente referente CInAP (Centro per l'integrazione Attiva e Partecipata – Servizi per le Disabilità e/o i DSA) del proprio Dipartimento (https://www.cinap.unict.it/content/referenti).
Esempi di domande e/o esercizi frequenti
L'esame consiste in una prova orale. Le domande frequenti riguardano
- 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
- Colorazione dei vertici e degli spigoli
- Reti di flusso
- Grafi fortemente connessi
- Durante la prova orale vengono richiesti alcuni Esempi ed applicazioni svolti durante le lezioni.