TEORIA DEI GRAFI

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).

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.ssa Daniele.

Si richiedono alcune conoscenze di base contenute nell' insegnamento di Geometria 1.

La frequenza è fortemente consigliata.

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, minimum spanning tree (MST) ed applicazioni.

Grafi planari: definizioni e primi teoremi, il teorema di Eulero, grafi planari massimali, non planarità di K₅ e K_3,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 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 (no dimostrazione) – Colorazione dei grafi planari, teorema dei 5 colori, teorema dei 4 colori (solo enunciato), 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 (solo enunciati).

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)

 Matroidi: Concetti e definizioni principali.

“Contributo dell’insegnamento agli obiettivi dell’Agenda 2030 per lo Sviluppo Sostenibile”.

 Goal 4: Istruzione e qualità. 

• obiettivo 4.4

Modalità:

“Contributo dell’insegnamento agli obiettivi dell’Agenda 2030 per lo Sviluppo Sostenibile”.

 Goal 6: Acqua pulita  e servizi igienico sanitari

obiettivo 6b

Modalità La Teoria dei Grafi può essere d'aiuto alla creazione di alcuni modelli per il miglioramento della gestione idrica e fognaria. Seminari o lezioni ad hoc basati sulla letteratura dell'applicazione della teoria dei grafi con gli esperti nel settore ingegneria idraulica

Goal 11:Città e comunità sostenibili 

• obiettivo 11.2 La Teoria dei Grafi può essere d'aiuto alla creazione di alcuni modelli per il miglioramento delle reti stradali, autostradali e metropolitane.

Modalità:

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

1. C. Berge, "Graph and Hypergraph", Elsevier.
2. Appunti del docente
3. M. Gionfriddo, Notes on Graph Theory 2018 (disponibili con il consenso del Prof. Emerito M. Gionfriddo)
4. R. J. Wilson,  Introduction to Graph Theory, Longman, 1996

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.

1. Grafi planari e loro proprietà.
2. Alberi e loro caratterizzazione. Alberi di economia
3. Grafi Euleriani ed Hamiltoniani.
4. Il problema del percorso minimo.
5. Teorema di Ford-Fulkerson.
6. Teorema di Köenig-Hall.
7. Teorema di Vizing.
8. Colorazione dei vertici e degli spigoli
9. Reti di flusso
10. Grafi fortemente connessi
11. Esempi ed applicazioni