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

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.

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

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.

1. C. Berge, "Graph and Hypergraph", Elsevier.
2. M. Gionfriddo, Notes on Graph Theory 2018 (disponibili con il consenso del Prof. Emerito M. Gionfriddo)
3. D. West, Introduction to Graph Theory
4. V. Voloshin, Introduction to Graph Theory

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.

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