Seguici su
Cerca

TEORIA DEI GRAFI

Anno accademico 2018/2019 - 3° anno - Curriculum GENERALE
Docente: Lorenzo Maria Filippo Milazzo
Crediti: 6
SSD: MAT/03 - Geometria
Organizzazione didattica: 150 ore d'impegno totale, 103 di studio individuale, 35 di lezione frontale, 12 di esercitazione
Semestre:

Obiettivi formativi

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 in aula tenute dal docente. In tali lezioni il programma vedrà suddiviso in sezioni: nozioni di base, grafi planari, cicli e cocicli, strutture connettive nei grafi, flussi nei grafi, accoppiamenti e coperture, colorabilità.

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.


Prerequisiti richiesti

Si richiedono conoscenze di base contenute negli insegnamenti di Geometria e Informatica.


Frequenza lezioni

La frequenza è fortemente consigliata.


Contenuti del corso

Definizioni di base della teoria dei grafi. Cicli e co-cicli, numero ciclomatico e co-cociclomatico. Grafi planari e loro proprietà. Formula di Eulero. Alberi e co-alberi. Lo "spanning tree". Grafi fortemente e minimalmente connessi, loro proprietà. Il problema del labirinto e dei minimi percorsi. Centri e raggi. Massimo flusso e massimo flusso compatibile. Teorema di Ford-Fulkerson. Accoppiamenti perfetti e massimi. Copertura e minima copertura di un grafo. Accoppiamenti nei grafi bipartiti. Teorema di Köenig. Percorsi hamiltoniani e euleriani. Colorazioni di spigoli, indice cromatico. Teorema di Vizing e sue implicazioni.


Testi di riferimento

C. Berge, "Graph and Hypergraph", Elsevier.



Programmazione del corso

 ArgomentiRiferimenti testi
1Numeri ciclomatico e co-ciclomaticoC. Berge, Graph and Hypergraph, Elsevier,  
2Grafi planariD. West, Introduction to Graph Theory 
3Grafi fortemente e minimamente connessiC. Berge, Graph and Hypergraph, Elsevier 
4Grafi di flusso, Teorema e algoritmo di Ford-FulkersonC. Berge, Graph and Hypergraph, Elsevier 
5Teorema di VizingC. Berge, Graph and Hypergraph, Elsevier 
6Matching e Teorema di KöenigD. West, introduction to Graph Theory, Illinois University 

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

Unica prova orale.


Esempi di domande e/o esercizi frequenti

  1. Grafi planari e loro proprietà.
  2. Relazione tra numeri ciclomatico e co-ciclomatico.
  3. Grafi fortemente e minimalmente connessi e loro proprietà.
  4. Il problema del percorso minimo.
  5. Teorema di Fordo-Fulkerson.
  6. Teorema di Köenig.
  7. Teorema di Vizing.
  8. Insiemi stabili e trasversali.