- Oggetto:
- Oggetto:
Teoria dei grafi (non attivo)
- Oggetto:
Graph Theory
- Oggetto:
Anno accademico 2018/2019
- Codice dell'attività didattica
- MFN1630
- Corso di studi
- Laurea in Matematica
- Anno
- 3° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- D.M. 270 TAF C - Affine o integrativo
- Crediti/Valenza
- 6
- SSD dell'attività didattica
- MAT/02 - algebra
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Scritto e Orale
- Prerequisiti
-
Argomenti di base di algebra e geometria. In particolare il concetto di gruppo, di determinante di una matrice quadrata e di spazio topologico.Basics of algebra and geometry. In particular the concept of group, of determinant of a square matrix and of topological space.
- Propedeutico a
-
Insegnamenti di algebra e geometria e di matematica applicata.Algebraic and geometry courses and applied math courses.
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
La teoria dei grafi, pur essendo una branca della matematica pura, ha numerose applicazioni nei più disparati settori della scienza e della tecnologia (ottimizzazione dei trasporti e delle risorse, architettura dei circuiti stampati, ecc.). L'insegnamento si propone di fornire agli studenti le conoscenze di base della teoria dei grafi e di renderli in grado di studiare e risolvere le problematiche collegate anche utilizzando gli algoritmi introdotti nelle lezioni.
Graph theory is part of pure mathematics, but it has many applications in
several sectors of science and technology. The aim of the course is to
give basics in graph theory with a particular attention to the algorithmic
aspects of the theory.- Oggetto:
Risultati dell'apprendimento attesi
Lo studente dovrà essere padrone degli argomenti, delle tecniche e degli algoritmi introdotti durante le lezioni. In particolare dovrà saper risolvere, utilizzando le tecniche proprie della teoria dei grafi, vari problemi di tipo combinatorio che nascono tanto in ambito teorico quanto nelle applicazioni. Dovrà saper maneggiare concetti quali la traversabilità, la planarità, le diverse etichettatura dei grafi.
The student will understand concepts, techniques and algorithms
introduced during the course. In particular, the student will be able to
solve, using graph theory techniques, various combinatorics problems
which originate both from theoretic and applied math. The student will handle concepts like traversability, planarity and labelling.- Oggetto:
Modalità di insegnamento
L'insegnamento è articolato in 48 ore di lezione frontale. Ampio spazio viene riservato agli esempi ed agli esercizi.
The course is articulated in 48 hours of formal in-class lecture time. A substantial part of the lectures will be reserved to examples and exercises.
- Oggetto:
Modalità di verifica dell'apprendimento
La prova scritta è costituita da esercizi; essa ha la durata di due ore e 30; durante questa prova è permesso consultare testi e appunti. La prova è valutata in 30simi. Per essere ammessi alla prova orale occorre raggiungere il punteggio di 18/30. La prova orale consiste in domande relative alla teoria e alle dimostrazioni presentate nelle lezioni. Durante la prova orale ci sarà una discussione degli errori della prova scritta. Scritto e orale devono essere sostenuti nella stessa sessione d'esame. Agli studenti stranieri è garantita la possibilità di sostenere l'esame in inglese.Written examination: exercises. Grade: 30-ths. It lasts 2h 30'. Students are allowed to bring books and notes. To be admitted to the oral examination it is required a grade 18 or more. Oral examination: questions about the contents and the proofs seen during the lessons of the course. There will be a discussion about the mistakes done in the written examination. Written and oral examinations must be taken in the same session. Foreign students may choose to take the exam in English- Oggetto:
Programma
Grafi e sottografi: grafi, sottografi, grafi speciali, operazioni sui grafi, successioni dei gradi. Grafi connessi e sconnessi: cammini e cicli, complemento di un grafo e grafi autocomplementari, vertici separanti e ponti, grafi euleriani, grafi hamiltoniani, blocchi. Matrici e alberi: grafi e matrici, alberi, il numero degli alberi non identici, alberi ricoprenti e teorema degli alberi e delle matrici. Grafi planari e non planari: la formula di Eulero, condizioni algebriche necessarie per la planarità, grafi planari e poliedri, omeomorfismo, caratterizzazione dei grafi planari. Cenni ad argomenti più avanzati, tempo permettendo.
Graphs and subgraphs. Special graphs. Operations on graphs. Degree sequences. Connected and disconnected graphs. Paths and cycles. Complementary graph. Autocomplementary graphs. Cut vertices and bridges. Eulerian graphs. Hamiltonian graphs Blocks. Matrices. Trees. The number of nonidentical trees. Spanning trees. Matrices and trees theorem. Planar and nonplanar graphs. Euler formula. Algebraic conditions to planarity. Planar graphs and polyhedra. Homeomorphism. Characterization of planar graphs. More advanced topics as time permits.
Testi consigliati e bibliografia
- Oggetto:
M. BURZIO - Dispense del Corso, disponibili in Materiale Didattico
M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt.
S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley.
M. BURZIO, Lectures notes, downloadable from Materiale Didattico
M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt.
S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley.
- Oggetto:
Orario lezioni
- Oggetto:
