Domenico LABBATE | TEORIA DEI GRAFI
TEORIA DEI GRAFI | |
---|---|
DIPARTIMENTO di MATEMATICA,INFORMATICA ed ECONOMIA | |
Laurea Magistrale | |
MATEMATICA | |
6 |
CFU | Ore | Ciclo | Docente | ||||
---|---|---|---|---|---|---|---|
1 | TEORIA DEI GRAFI | ||||||
6 | 48 | Secondo Semestre | LABBATE Domenico |
Lingua insegnamento | italiano (inglese su richiesta) |
---|
Obiettivi formativi e risultati di apprendimento | Apprendimento definizioni e teoremi fondamentali di teoria dei grafi. Apprendimento e sviluppo tecniche di dimostrazione della teoria dei grafi. Utilizzo delle tecniche per l'approccio allo studio di problemi aperti della teoria dei grafi. Apprendimento di cenni di ottimizzazione combinatoria. Relazioni tra combinatoria, algebra e geometria in tale ambito. |
---|
Prerequisiti | corsi triennale geometria e algebra di base (consigliati) |
---|
Contenuti del corso | Teoria dei grafi e applicazioni |
---|
Programma esteso | 1. Introduzione Origini della teoria dei grafi. Il problema dei ponti di Könisberg, i problemi del commesso viaggiatore e del giro intorno al mondo, il teorema dei 4 colori. 2. Grafi e sottografi Definizioni ed esempi Grafi. Vertici e spigoli di un grafo. Loop e spigoli multipli. Multigrafi, grafi semplici, grafi finiti e infiniti. Ordine e side di un grafo. Esempi ed esercizi. Isomorfismo tra grafi Grafi identici. Grafi isomorfi. Grafo completo, vuoto o banale, bipartito, bipartito completo. Esempi. Numero di spigoli di un grafo completo, grafo bipartito e grafo bipartito completo. Esercizi. Il complemento di un grafo. Le matrici di incidenza e di adiacenza Le matrici di incidenza e di adiacenza di grafi semplici e multigrafi. Esempi ed esercizi. Sottografi Sottografo proprio ed improprio. Supergrafo. Sottografo generatore e soggiacente (underlying). Sottografo indotto dai vertici di un grafo. Grafo resto o residuo. Esempi. Sottografo indotto dagli spigoli di un grafo. Sottografo somma. Sottografi disgiunti. Sottografo unione. Intersezione di sottografi. Valenza o grado Il grado o valenza di un vertice. Valenza minima e massima di un grafo. Il lemma delle valenze e sue conseguenze. Grafi k-regolari. Vertici iniziali e finali di un grafo. Esempi ed esercizi. Cammini e connessione Definizione di cammino (walk), tracciato (trail), percorso (path) e loro lunghezze. Esempi. Vertici connessi. Componenti (connesse) di un grafo. Grafo disconnesso. Distanza e diametro di un grafo. Circuiti o cicli Cammino chiuso. Ciclo o circuito di un grafo. k-ciclo. Cicli pari e dispari. Caratterizzazione dei grafi bipartiti in base ai loro cicli. Valenza minima e cicli in un grafo. Il girth di un grafo. Esempi. 3. Alberi Generalitā e caratterizzazione Definizione foresta e albero. Ponte o bridge di un grafo. Teorema di caratterizzazione degli alberi. Corollario su foresta. Alberi generatori e loro proprietā. Esempi ed esercizi. Formula di Cayley Operazione di contrazione di uno spigolo. Grafo contratto e sue proprietā. Teorema sul numero di alberi generatori di un grafo. Formula di Cayley. 4. Connessione Connettivitā Spigolo di taglio (cut edge) o bridge (altra definizione). Vertice di taglio (cut vertex). Insieme separatore (k-vertex cut). Connettivitā di un grafo. Grafo k-connesso. Insieme di taglio (cutset o edge cut) e k-edge cut. Connettivitā per spigoli. Grafo k-connesso per spigoli. Esempi. Relazione fondamentale tra k-connessione, k-connessione per spigoli e valenza minima di un grafo. Caso del grafo cubico semplice. Blocchi Blocchi di un grafo. Blocchi e 2-connessione. Path internamente disgiunti. Il teorema di Whitney e sue conseguenze. Suddivisione di uno spigolo. Blocchi e vertici su di un ciclo comune. Caratterizzazione dei grafi 2-connessi per spigoli. Teorema di Menger (senza dim.). 5. Grafi euleriani ed hamiltoniani Tour euleriani Trail euleriano. Tour e tour euleriano. Grafo euleriano. Caratterizzazione dei grafi euleriani. Corollario sui trail euleriani e su Kn. Cicli hamiltoniani Path e ciclo hamiltoniano, grafo hamiltoniano, teorema sulle componenti di un grafo hamiltoniano. Esempi e controesempi dell'esistenza dei circuiti hamiltoniani. Teorema di Dirāc. L'(x,y)-lollipop. Lemma del lollipop (senza dim.). Dimostrazione di Bondy del teorema di Dirāc. Corollario sui path hamiltoniani. Teorema di Ore e sue conseguenze. Chiusura di un grafo. Teorema della chiusura o di Bondy-Chvātal e sue conseguenze. Generalizzazione di Fan del teorema di Ore (senza dim.). Grafi unicamente hamiltoniani e congettura di Sheehan. 6. Accoppiamenti Generalitā Accoppiamento M in un grafo. Vertici accoppiati. Accoppiamenti M-saturated e M-unsaturated. Accoppiamenti perfetti o 1-fattori di un grafo. Esempi. r-fattori di un grafo. Esempi di 2-fattori. 1-fattorizzazione e k-fattorizzazione di un grafo. Esempi. Accoppiamento massimo. Path M-alternante e M-aumentante. Teorema di Berge sugli accoppiamenti massimi. Accoppiamenti e ricoprimenti in grafi bipartiti Ricoprimento (di vertici) di un grafo. Ricoprimento minimo. Teorema di König sulla massima cardinalitā di un accoppiamento e minima cardinalitā di un ricoprimento (senza dim.). Neighbour o adiacenze di un vertice. Insieme dei neighbour. Condizione necessaria per l'esistenza di un accoppiamento di un grafo bipartito. Condizione matrimoniale. Teorema di Hall sull'esistenza di accoppiamenti di un grafo bipartito. Corollario: il Marriage theorem sull'esistenza di 1-fattori di un grafo bipartito regolare. Estensione al caso dell'esistenza di 1-fattorizzazioni. Teorema di König-Ore sulla cardinalitā massima di un accoppiamento in un grafo bipartito (senza dim). Teorema di Petersen sui 2-fattori. Accoppiamenti perfetti in grafi generali Condizione necessaria sull'esistenza di 1-fattori in grafi generali e controesempi. Componente dispari o pari di un grafo. Teorema di Tutte sull'esistenza di 1-fattori con dim. di Lovāsz. 1-barriere e condizione di Tutte. Corollario di Petersen. 7. Colorazioni di un grafo Colorazione sui vertici di un grafo Colorazione sui vertici. k-colorazione e numero cromatico. Grafo k-colorabile e k-cromatico. Esempi. Caratterizzazioni sul numero cromatico di un grafo legate alla valenza massima e/o regolaritā del grafo. Numero cromatico di un grafo bipartito. Teorema di Brooks. Colorazione sugli spigoli di un grafo Colorazione e k-colorazione sugli spigoli. Indice cromatico. Teorema di Vizing. Grafi di classe 1 e 2. Esempi fondamentali: il ciclo Cn, il grafo di Petersen. Conseguenza: il grafo di Petersen non č 1-fattorizzabile. Teorema sulle classi di un grafo completo. Applicazione: equivalenza con 1-fattorizzazioni di tale grafo. Caratterizzazione sulla classe 1 dei grafi bipartiti. 8. Grafi Planari Generalitā Immersione planare di un grafo. Grafo planare. Curve di Jōrdan. Teorema di Jōrdan sulle curve (senza dim.). K5 e K3,3 non sono planari.
La formula di Eulero Regioni o facce di un grafo. Lemma sulle valenze delle facce di un grafo. Formula di Eulero e diverse sue conseguenze sulle limitazioni superiori e inferiori del numero di spigoli e vertici di un grafo planare con e senza triangoli. Dimostrazione della non planaritā di K5 e K3,3. Grafi planari massimali e loro numero di spigoli. I teoremi dei 4 e 5 colori Il teorema di Heawood sulla 5-colorabilitā di un grafo planare. Teorema dei 4 colori (cenni sulla dimostrazione effettuata da Robertson, Sanders, Seymour e Thomas nel 1998 e su quella detta precedente ma computer-based di Appel e Haken del 1977). Il teorema di Kuratowski Ogni sottografo proprio di K5 e K3,3 č planare. Lemmi su suddivisioni e sottografi planari. Caratterizzazione dei grafi planari non minimali con valenza minima almeno 3 (senza dim). Teorema di Kuratowski. 9. Parametri e classi fondamentali di grafi hamiltoniani Parametri fondamentali e grafi hamiltoniani (a) Connessione e grafi hamiltoniani: Teorema di Dirāc sui grafi k-connessi con insiemi di k vertici e sua generalizzazione al caso dei grafi hamiltoniani (senza dim.). Generalizzazione teorema di Ore per grafi semplici 2-connessi. (b) Numero di stabilitā e grafi hamiltoniani: insieme stabile o indipendente, numero di stabilitā o indipendenza. Teorema di Chvātal-Erdōs. Generalizzazione del concetto di ponte. C-bypass. Dimostrazione teorema Chvātal-Erdōs. Corollario su path hamiltoniani. (c) Accoppiamenti e grafi hamiltoniani: numero d'accoppiamenti. Teorema di Häggkvist (senza dim.). Teorema di Jackson-Wormald: generalizzazione del teorema di Dirāc (senza dim.). Classi fondamentali di grafi hamiltoniani (a) Grafi planari: Congettura di Barnette. Teorema di Tutte (cenni sulla dim.). (b) Grafi regolari: Il grafo di Heawood. Esistenza di grafi non hamiltoniani d-regolari d-connessi. Teorema di Smith sul numero di circuiti hamiltoniani e conseguenze (senza dim.). Lemma del lollipop versione hamiltoniana. Corollario di Thomasson sul numero pari di circuiti hamiltoniani nei grafi di valenza dispari. Validitā congettura Sheehan per multigrafi. Teoremi di Robinson-Wormald, Richmond et al., Jackson (tutti senza dim.). 10. Accoppiamenti e invarianti algebrici Preliminari Matrice d'adiacenza bipartita o ridotta di un grafo bipartito e sue proprietā. Esempi. Il determinante e il permanente di un grafo. Grafi det-estremali. 1-fattori, determinanti e permanenti Il determinante e gli 1-fattori. I grafi bipartiti privi di 1-fattori hanno il determinante nullo. Il permanente č uguale al numero di 1-fattori distinti in un grafo bipartito. Il grafo di Heawood č det-estremale. Matrici doppiamente stocastiche. Disuguaglianze di Falikman-Egorycév. Congettura di Minc e dimostrazione di Schrijver-Brégman e sue conseguenze. Teorema di Schrijver-Valiant Disuguaglianza di Voorhoeve. 11. 1-fattorizzazioni (cenni) Lo studio delle 1-fattorizzazioni di grafi completi. La congettura delle 1-fattorizzazioni. Costruzioni di 1-fattorizzazioni su un grafo completo d'ordine pari. 12. Classi di grafi con condizioni su 1- e 2-fattori(cenni estesi) I grafi minimamente 1-fattorizzabili e loro studio con permanente e determinante. I grafi det-estremali. I grafi Pfaffiani. I grafi 2-fattori ha miltoniani e relazioni tra essi. Diversi tipi di dimostrazione di alcune loro proprietā. 13. Snarks Importanza degli snarks nella teoria dei Grafi moderna. Definizioni, proprietā, esempi e costruzioni di snarks. Il lemma di Blanusa (parity lemma), il prodotto dot e le superposizioni. Relazioni tra snarks e 2-fattori. Congetture famose di teoria dei grafi che hanno gli snarks come possibile contro esempio. 14. Network flow theory (teoria delle reti di flusso) e connettivitā Flow, Cut, il teorema del Max-Flow Min-Cut, l'algoritmo di FordFulkerson , Path diretti disgiunti per archi, Circulation, Mengers Theorem. Connectivity and Local Connectivity, Vertex Cuts and Mengers Theorem, The Fan Lemma, Edge Connectivity, Essential Edge Connectivity Connectivity in Digraphs. NOTA: Tranne nei casi specificati i teoremi si intendono dimostrati. |
---|
Metodi didattici | Lezione frontale con utilizzo di Ipad e/o PC |
---|
Modalitā di verifica dell'apprendimento | esame orale |
---|
Testi di riferimento e di approfondimento, materiale didattico Online | Bibliografia: - J.A. Bondy, U.S.R. Murty. Graph Theory. Springer (nuova edizione) - J.A. Bondy, U.S.R. Murty. Graph Theory with Applications. Elsevier North-Holland (vecchia edizione scaricabile gratuitamente sul sito di Adrien Bondy in pdf) - L. Lovāsz, P. Plummer. Matching Theory. Elsevier North-Holland. - Handbook of Combinatorics. Vol. I North Holland. - Holton, Sheehan. The Petersen Graph. Cambridge Univ. Press. - Appunti del corso in pdf. |
---|
Metodi e modalitā di gestione dei rapporti con gli studenti | Frontale, ricevimento, mailing list, cartella dropbox condivisa per file pdf corso. Le date esame possono essere concordate con il docente a prescindere da quelle fissate a seconda degli impegni degli studenti e del docente. Il ricevimento sarā nei giorni seguenti Martedė 11:30-13:30, Mercoledė 11:00-13:00 e per appuntamento. Il docente č presente ogni giorno (salvo imprevisti) nel suo studio pertanto se libero fornirā sempre ricevimento. |
---|
Date di esame previste | Gennaio 2021 22 Febbraio 2021 - Marzo 2021 - Aprile 2021. - Maggio 2021 20 Giugno 2021 8 Luglio 2021 2 Agosto 2021 - Settembre 2021 3 Ottobre 2021 1 Novembre 2021 - Dicembre 2021 - |
---|
Seminari di esperti esterni | I seminari di esperti se presenti per ricerca con il docente durante il periodo del corso sono previsti |
---|
Altre informazioni | - |
---|
![Domenico LABBATE](http://service.unibas.it/documenti/docenti_foto/002431_IMG_20170816_120001.jpg)