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

Geometria

La frequenza è fortemente consigliata.

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. Colorazioni di vertici e insiemi stabili, numero cromatico. Polinomio cromatico. Decomposizione di grafi completi in terne: i sistemi di terne. Bicolorazioni di sistemi di terne. Numero cromatico superiore e inferiore.

1. C. Berge, "Graph and Hypergraph", Elsevier.
2. D. West, "Introduction to Graph Theory", Illinois University.

Unica prova orale.

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.
9. Bicolorazioni.