Obiettivi Formativi

Il corso fornisce allo studente i primi elementi della teoria dei grafi, illustrandone anche alcune applicazioni a problemi pratici. L'obiettivo e' quello di trasmettere agli studenti, non soltanto le principali conoscenze specifiche della teoria dei grafi quali le condizioni algebriche, la planarità, le colorazioni, ma anche nello stesso tempo, dando particolare attenzione al rigore delle dimostrazioni e delle notazioni, il miglioramento delle capacita' di comprensione, nonché delle abilita' espressive ed espositive. Inoltre si introducono alcuni algoritmi sulle principali problematiche trattate. Metodi di accertamento: sono previste delle verifiche in itinere, seguite da prove scritte ed eventualmente da una interrogazione orale. Le prove sono valutate in trentesimi e la soglia di sufficienza prevista per il superamento di ogni prova è 18/30.

Metodi didattici

Gli argomenti del programma sono esposti in progressione logica per facilitarne l'apprendimento. Le lezioni teoriche sono intervallate dallo svolgimento di esercizi a chiarimento ed approfondimento delle nozioni esposte. Il linguaggio adottato possiede sempre caratteristiche di chiarezza, semplicità e sufficiente rigore. A supporto didattico vengono usati videoproiettore e tavoletta grafica.

Prerequisiti

Fondamenti di combinatoria e di algebra lineare.

Verifiche dell'apprendimento

Sono previste delle verifiche in itinere seguite da una prova scritta e una possibile prova orale. Le prove sono valutate in trentesimi e la soglia di sufficienza prevista per il superamento di ogni prova è 18/30.

Programma del Corso

INTRODUZIONE Approccio intuitivo alla nozione di grafo. Uno sguardo ai problemi storici e alle applicazioni più note della teoria dei grafi. DEFINIZIONI ED ESEMPI Terminologia e definizioni. Esempi di grafi: grafi nulli, completi, regolari, platonici, bipartiti, unione e somma di grafi, connessi, ciclici, ruote. CAMMINI E GRAFI CICLICI Altre definizioni. Grafi euleriani. Grafi hamiltoniani. Grafi infiniti. ALBERI Proprietà elementari degli alberi. La classificazione degli alberi: il teorema di Cayley. Alcune applicazioni della teoria dei grafi. PLANARITA’ E DUALITA’ Grafi planari. Il teorema di Eulero sui grafi piani. Grafi duali. LA COLORAZIONE DEI GRAFI Il numero cromatico. La congettura dei quattro colori. La colorazione delle mappe. Colorazione degli spigoli di un grafo. Polinomi cromatici. GRAFI ORIENTATI Definizione. Grafi orientati euleriani e tornei.