Domenico LABBATE | MATEMATICA DISCRETA

Italiano (Inglese su richiesta o in presenza di studenti Erasmus)

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.

corsi triennale geometria e algebra di base (consigliati)

I grafi e le loro applicazioni

Programma 2019-2020

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.

NOTA: Tranne nei casi specificati i teoremi si intendono dimostrati.

Lezione frontale con utilizzo di Ipad e/o PC

Esame orale

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.

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.

Gennaio2020 23

Febbraio2020 -

Marzo2020 -

Aprile2020 -

Maggio2020 20

Giugno2020 3

Luglio2020 2

Agosto2020 -

Settembre2020 3

Ottobre2020 1

Novembre2020 -

Dicembre 2020 -

Si

I seminari suddetti vi saranno solo se nel periodo del corso si troveranno quali ospiti colleghi che svolgono ricerca con il sottoscritto. Inoltre gli studenti potranno avere diverse date di esame dopo aver contattato il docente 1/2 settimane prima della data richiesta.