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.

Learning Goals

The course provides the student with the first elements of graph theory, also illustrating some applications to practical problems. The aim is to give to the students, not only the main specific knowledge of graph theory such as algebraic conditions, the planarity, the colourings, but also at the same time, particular attention to the rigor of the proofs and the notations, the improvement of capacity of understanding, as well as expressive and presentative skills. In addition, we introduce some algorithms on the main issues addressed. Methods of assessment: there are audits in progress, followed by written tests and possibly an oral examination. The tests are evaluated on a scale of thirty and the threshold of sufficiency scheduled for passing each test is 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.

Teaching Methods

The topics of the program are presented in a logical progression to facilitate learning. The lectures are interspersed by completion of exercises to clear and deepen the concepts presented. The language has always the characteristics of clarity, simplicity and sufficient rigor. Video projector and graphics tablet are used as a teaching aid.

Prerequisiti

Fondamenti di combinatoria e di algebra lineare.

Prerequisites

Fundamentals of linear algebra and combinatorics.

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.

Assessment

The exams consist of one or more audits in progress followed by written tests and possible oral questions. The grades are on a scale of 30 and the threshold of sufficiency scheduled for passing each test is 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.

Course Syllabus

INTRODUCTION Intuitive approach to the notion of graph. A look at the historical problems and the most popular applications of graph theory. DEFINITIONS AND EXAMPLES Terminology and definitions. Examples of graphs: null, complete, regular, platonic, bipartite graphs, union and sum of graphs, connected, cyclic, wheel graphs. PATHS AND CYCLIC GRAPHS Other definitions. Eulerian graphs. Hamiltonian graphs. Infinite graphs. TREES Elementary properties of the trees. The classification of trees: the theorem of Cayley. Some applications of graph theory. PLANARITY AND DUALITY Planar graphs. Euler's theorem on planar graphs. Dual graphs. THE COLOURING OF THE GRAPHS The chromatic number. The four color theorem. The colouring of maps. Colouring of the edges of a graph. Chromatic polynomials. DIRECTED GRAPHS Definition. Eulerian directed graphs and tournaments.