Offerta Didattica

 

MATEMATICA

TEORIA DEI GRAFI

Classe di corso: L-35 - Scienze matematiche
AA: 2015/2016
Sedi: MESSINA
SSDTAFtipologiafrequenzamoduli
MAT/03A scelta dello studenteLiberaLiberaNo
CFUCFU LEZCFU LABCFU ESEOREORE LEZORE LABORE ESE
64025232020
Legenda
CFU: n. crediti dell’insegnamento
CFU LEZ: n. cfu di lezione in aula
CFU LAB: n. cfu di laboratorio
CFU ESE: n. cfu di esercitazione
FREQUENZA:Libera/Obbligatoria
MODULI:SI - L'insegnamento prevede la suddivisione in moduli, NO - non sono previsti moduli
ORE: n. ore programmate
ORE LEZ: n. ore programmate di lezione in aula
ORE LAB: n. ore programmate di laboratorio
ORE ESE: n. ore programmate di esercitazione
SSD:sigla del settore scientifico disciplinare dell’insegnamento
TAF:sigla della tipologia di attività formativa
TIPOLOGIA:LEZ - lezioni frontali, ESE - esercitazioni, LAB - laboratorio

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.

Testi di riferimento: Robin J. Wilson: Introduction to Graph Theory, Fourth edition, Prentice Hall publisher.

Elenco delle unità didattiche costituenti l'insegnamento

TEORIA DEI GRAFI

Docente: MARIO DE SALVO

Orario di Ricevimento - MARIO DE SALVO

GiornoOra inizioOra fineLuogo
Lunedì 12:00 13:00Si riceve per appuntamento da concordare con il docente via e-mail all'indirizzo desalvo@unime.it , presso l'Incubatore di impresa, piano 1, stanza 12.
Martedì 12:00 13:00Si riceve per appuntamento da concordare con il docente via e-mail all'indirizzo desalvo@unime.it , presso l'Incubatore di impresa, piano 1, stanza 12.
Note:
  • Segui Unime su:
  • istagram32x32.jpg
  • facebook
  • youtube
  • twitter
  • UnimeMobile
  • tutti