1015531 -
TEORIA DEI GRAFI
-
GUARDO ELENA MARIA
( programma)
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 K5 e K3,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.
C. Berge, "Graph and Hypergraph", Elsevier. M. Gionfriddo, Notes on Graph Theory 2018 (disponibili con il consenso del Prof. Emerito M. Gionfriddo) D. West, Introduction to Graph Theory V. Voloshin,Introduction to Graph Theory
-
GIONFRIDDO Mario
( programma)
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 K5 e K3,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 Theory4. V.Voloshin,Introduction toGraphTheory
|
9
|
MAT/03
|
49
|
24
|
-
|
-
|
-
|
Attività formative caratterizzanti
|
ITA |