06690 - TEORIA DEI GRAFI

Anno Accademico 2021/2022

  • Docente: Marilena Barnabei
  • Crediti formativi: 6
  • SSD: MAT/02
  • Lingua di insegnamento: Italiano
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea Magistrale in Matematica (cod. 5827)

    Valido anche per Laurea Magistrale in Matematica (cod. 8208)

Conoscenze e abilità da conseguire

Alla fine del corso lo studente conosce le nozioni ed i risultati fondamentali della teoria dei grafi ed è in grado di studiare le problematiche collegate, relative a vari settori della scienza e della tecnologia.

Contenuti

Definizione di grafo e di grafo semplice. Grado di un vertice. Matrice di adiacenza e matrice di incidenza. Esempi: grafi completi, circuiti, ruote, cubi.

Sottografo. Isomorfismo tra grafi.

Grafo connesso. Componenti connesse di un grafo. Relazione tra numero di lati e numero di vertici in un grafo connesso e semplice. Ponti e punti di articolazione. Grafo bipartito. Teorema: un grafo è bipartito se e solo se non contiene cicli di lunghezza dispari.

Alberi e foreste. Teorema: ogni albero possiede almeno due vertici di grado 1. Teorema: un albero con n vertici ha n–1 lati.

Teorema di Cayley sul numero di alberi con n vertici. Albero generatore. Teorema: ogni grafo connesso possiede un albero generatore. Algoritmo di visita in profondità e algoritmo di visita in ampiezza.

Matrici di adiacenza e di incidenza di un grafo. Prime proprietà. Laplaciano di un grafo. Teorema degli alberi generatori.

Grafi Euleriani e loro caratterizzazione. Algoritmo di Fleury. Grafi Hamiltoniani. Teorema di Ore sui grafi Hamiltoniani. Teorema di Dirac.

Grafo dei lati. Teorema: se un grafo è Euleriano, il suo grafo dei lati è sia Euleriano che Hamiltoniano.

Matching in un grafo: definizione ed esempi. Matching perfetto. Matching massimale e massimo. Cammino aumentante. Condizione necessaria e sufficiente affinché un matching sia massimo.

Matching nei grafi bipartiti: teorema di Hall e sue conseguenze. Vertex cover. Relazione tra la cardinalità di un vertex cover minimo e quella di un matching massimo. Esempi.

Teorema di Koenig-Egervary: in un grafo bipartito la cardinalità di un vertex cover minimo è uguale a quella di un matching massimo. Nozione di insieme indipendente di vertici e di edge cover. Relazione tra le varie cardinalità. Teorema di Gallai e sue conseguenze.

Matching nei grafi qualsiasi: esempi. Algoritmo del matching perfetto. Teorema di Tutte: condizione necessaria e sufficiente affinché un grafo possieda un matching perfetto.

Grafi planari e grafi piani. Facce di un grafo piano. Duale di un grafo piano.

Contrazione di un grafo rispetto ad un lato. Formula di Eulero per i grafi planari e sue conseguenze. Solidi platonici.

Colorazioni di grafi. Numero cromatico. Teorema di Koenig: un grafo semplice ha numero cromatico 2 se e solo se è bipartito. Limitazioni superiori ed inferiori per il numero cromatico di un grafo. Algoritmo euristico di colorazione.

Colorazione ottima di un grafo semplice ottenuta risolvendo un problema di programmazione lineare. Colorazione dei grafi planari. Teorema dei cinque colori. Cenni sul teorema dei quattro colori.

Polinomio cromatico di un grafo semplice e sue proprietà: ricorrenza, monicità, interpretazione del coefficiente di xn–1. Polinomio di Tutte di un grafo: definizione, proprietà e sua relazione con il polinomio cromatico.

Grafo orientato: definizione e nomenclatura di base. Orientazioni acicliche di un grafo non orientato. Teorema: il numero di orientazioni acicliche è il valore assoluto della valutazione in (–1) del polinomio cromatico.

Grafo associato ad una griglia di sudoku. Teorema: il numero cromatico di un grafo di sudoku di lato n2 è esattamente n2.

Colorazioni parziali e polinomio associato.

Grafi perfetti: definizione e proprietà. Esempi di grafi perfetti: grafi bipartiti. Grafi di confrontabilità di un ordine parziale: Teoremi di Mirsky e di Dilworth. Teorema di Lovasz: il complementare di un grafo perfetto è perfetto. Il complementare di un grafo bipartito è perfetto: connessione con il teorema di Koenig. Il grafo delle inversioni di una permutazione è perfetto.

Connessione per vertici. Numero di connessione di un grafo. Limitazioni superiori per il numero di connessione. Grafi di Harary.

Connessione per lati e numero relativo. Legame tra numero di connessione per vertici, numero di connessione per lati e grado minimo dei vertici. Taglio in un grafo. Relazione tra insiemi separatori di lati e tagli.

Reti. Flusso in una rete. Algoritmo di Ford-Fulkerson per la costruzione di un flusso massimo. Teorema del flusso massimo - taglio minimo e sue conseguenze.

Testi/Bibliografia

Reinhard Diestel. Graph Theory. Electronic Edition 2000 cс Springer-Verlag New York

Metodi didattici

Lezioni frontali.

Modalità di verifica e valutazione dell'apprendimento

Per ogni allievo l'esame consiste in una prova orale tesa ad accertare la conoscenza dei concetti presentati nel corso e la capacità dello studente di avere compreso e di esporre correttamente sia le connessioni tra i vari argomenti svolti, sia le dimostrazioni dei principali risultati visti durante il corso.

Orario di ricevimento

Consulta il sito web di Marilena Barnabei