06690 - TEORIA DEI GRAFI

Scheda insegnamento

  • Docente Marilena Barnabei

  • Crediti formativi 6

  • SSD MAT/02

  • Modalità di erogazione In presenza (Convenzionale)

  • Lingua di insegnamento Italiano

  • Orario delle lezioni dal 20/02/2018 al 24/05/2018

Anno Accademico 2017/2018

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 applicarli in problemi di varia natura che si presentano nell'insegnamento secondario.

Programma/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. Teorema: in un grado connesso esiste un etichettamento dei vertici v_1,...,v_n tale ogni sottografo v_1,...,v_i sia connesso per ogni i. 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à. 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.

Grafo associato ad un insieme di trasposizioni del gruppo simmetrico S_n. Condizione necessaria e sufficiente affinché il prodotto di n-1 trasposizioni di S_n sia un ciclo di lunghezza n.

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 x^(n-1).

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 n^2 è esattamente n^2.

Colorazioni parziali e polinomio associato.

Grafi perfetti: definizione e proprietà. Esempi di grafi perfetti: grafi bipartiti. Grafi di confrontabilità di un ordine parziale. Teorema di Lovasz: il complementare di un grafo perfetto è perfetto (senza dim.). 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. Teorema di Menger.

Grafi 2-connessi e relativa caratterizzazione. Addizione per cammino e sintesi di Whitney di un grafo. Teorema: ogni grafo 2-connesso è la sintesi di Whitney di un circuito.

Testi/Bibliografia

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

Metodi didattici

Lezioni frontali.

Modalità di verifica 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