Presentazione

Organizzazione della Didattica

DM270
MATEMATICA


6

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 24 24 0 150

Periodo

AnnoPeriodo
III anno2 semestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
02/03/201512/06/2015

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteFormazione modellistico-applicativaMAT/096


Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. CONFORTI MICHELANGELOMAT/09Dipartimento di Matematica

Altri Docenti

Non previsti.

Attività di Supporto alla Didattica

Non previste.

Bollettino

Nessun prerequisito

Ihntroduzione alla teoria dei grafi ed alla matematica discreta

Teoria ed esercizi svolti in classe.

Definizioni preliminari {1.2}Sottografi} {1.2.1}Contrazione, minori} {1.3}Cammini, cicli, tagli e connettivita' {1.4}Alcune classi di grafi {1.4.1}Isomorfismo tra grafi {2}Arcoconnettivit\'a {2.1}Definizioni {2.2}Arcoconnettivit\'a e contrazione {2.3}Il teorema di Menger {2.4}L'algoritmo di Nagamochi ed Ibaraki {2.5}Albero di Gomory-Hu {2.5.1}Submodularità della funzione taglio {2.5.2}Esistenza e computazione dell'albero di Gomory-Hu {3}Grafi orientati {3.1}Definizioni {3.2}Teorema di Menger per grafi orientati {3.3}Calcolo di massimo flusso e minimo taglio tra due vertici {4}Separatori e connettività sui vertici {4.2}Terza formulazione del Teorema di Menger {5}Albero ricoprente di peso minimo}{57} {5.1}Definizioni, algoritmo di Kruskal {5.2}Basi di matrici di incidenza in GF$_2$ {5.3}Matroidi e algoritmo greedy {6}Grafi k-connessi {6.1}Definizioni e proprietà generali {6.2}Grafi 2-connessi {6.2.1}Applicazione della 2-connessione allo studio dei grafi fortemente connessi {6.3}Ancora sui grafi k-connessi {6.4}Grafi 3-connessi {6.5}Splitting-off e applicazioni {6.5.1}Splitting-off {6.5.2}Weak orientation theorem {6.5.3}Aumento dell'arcoconnettività {7}Matching {7.1}Definizioni, condizioni di ottimalità di un matching {7.1.1}Cammini aumentanti {7.2}Grafi bipartiti {7.2.1}Trasversali {7.3}Grafi nonbipartiti {7.4}Edge-coloring {7.4.1}Definizioni, teorema di Vizing {7.4.2}Grafi $k-$regolari {8}Planarità {8.1}Definizioni e primi risultati {8.1.1}Formula di Eulero {8.2}Teorema di Kuratowski {9}Colorazione dei vertici {9.1}Teorema dei $4$ colori e generalizzazioni {9.3}Congettura di Hadwinger e Teorema di Mader {10}Cicli hamiltoniani e tour euleriani {10.1}Definizioni, condizioni necessarie per l'esistenza di un ciclo hamitloniano {10.2}Condizioni sufficienti per l'esistenza di un ciclo hamiltoniano {10.2.1}La chiusura di un grafo {10.4}Tour euleriani

Esame scritto

Esercizi tendenti ad accertate sia la conoscenza della materia che la capacita' di fornire elementari dimostrazioni in maniera autonoma.

A. Bondy U. S. Murty, Graph Theory. : Springer, 2008

Dispense fornite dal docente.

Nessun prerequisito

Ihntroduzione alla teoria dei grafi ed alla matematica discreta

Teoria ed esercizi svolti in classe.

Definizioni preliminari {1.2}Sottografi} {1.2.1}Contrazione, minori} {1.3}Cammini, cicli, tagli e connettivita' {1.4}Alcune classi di grafi {1.4.1}Isomorfismo tra grafi {2}Arcoconnettivit\'a {2.1}Definizioni {2.2}Arcoconnettivit\'a e contrazione {2.3}Il teorema di Menger {2.4}L'algoritmo di Nagamochi ed Ibaraki {2.5}Albero di Gomory-Hu {2.5.1}Submodularità della funzione taglio {2.5.2}Esistenza e computazione dell'albero di Gomory-Hu {3}Grafi orientati {3.1}Definizioni {3.2}Teorema di Menger per grafi orientati {3.3}Calcolo di massimo flusso e minimo taglio tra due vertici {4}Separatori e connettività sui vertici {4.2}Terza formulazione del Teorema di Menger {5}Albero ricoprente di peso minimo}{57} {5.1}Definizioni, algoritmo di Kruskal {5.2}Basi di matrici di incidenza in GF$_2$ {5.3}Matroidi e algoritmo greedy {6}Grafi k-connessi {6.1}Definizioni e proprietà generali {6.2}Grafi 2-connessi {6.2.1}Applicazione della 2-connessione allo studio dei grafi fortemente connessi {6.3}Ancora sui grafi k-connessi {6.4}Grafi 3-connessi {6.5}Splitting-off e applicazioni {6.5.1}Splitting-off {6.5.2}Weak orientation theorem {6.5.3}Aumento dell'arcoconnettività {7}Matching {7.1}Definizioni, condizioni di ottimalità di un matching {7.1.1}Cammini aumentanti {7.2}Grafi bipartiti {7.2.1}Trasversali {7.3}Grafi nonbipartiti {7.4}Edge-coloring {7.4.1}Definizioni, teorema di Vizing {7.4.2}Grafi $k-$regolari {8}Planarità {8.1}Definizioni e primi risultati {8.1.1}Formula di Eulero {8.2}Teorema di Kuratowski {9}Colorazione dei vertici {9.1}Teorema dei $4$ colori e generalizzazioni {9.3}Congettura di Hadwinger e Teorema di Mader {10}Cicli hamiltoniani e tour euleriani {10.1}Definizioni, condizioni necessarie per l'esistenza di un ciclo hamitloniano {10.2}Condizioni sufficienti per l'esistenza di un ciclo hamiltoniano {10.2.1}La chiusura di un grafo {10.4}Tour euleriani

Esame scritto

Esercizi tendenti ad accertate sia la conoscenza della materia che la capacita' di fornire elementari dimostrazioni in maniera autonoma.

A. Bondy U. S. Murty, Graph Theory. : Springer, 2008

Dispense fornite dal docente.