- Oggetto:
- Oggetto:
Teoria dei grafi
- Oggetto:
Graph Theory
- Oggetto:
Anno accademico 2015/2016
- Codice dell'attività didattica
- MFN1630
- Docente
- Prof. Giorgio Ferrarese (Titolare del corso)
- Corso di studi
- Laurea in Matematica
- Anno
- 3° anno
- Periodo didattico
- Primo semestre
- Tipologia
- D.M. 270 TAF C - Affine o integrativo
- Crediti/Valenza
- 6
- SSD dell'attività didattica
- MAT/02 - algebra
- Modalità di erogazione
- Doppia
- 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à ottenere padronanza con gli argomenti, le tecniche e gli algoritmi introdotti durante le lezioni. In particolare dovrà dimostrare di 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à dimostrare di saper maneggiare concetti quali la traversabilità, la planarità, le diverse etichettatura dei grafi.
The student will understand arguments,techniques and algurithms
introduced during the course. In particular, the student will be able to
solve, using graph theory techniques,different combinatorics problems
which spring both in theoretic and applied math. The student will prove
to have understood 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 è costitutita da esercizi. La prova è valutata in 30simi. Per essere ammessi alla prova orale occorre raggiungere il punteggio di 15/30. La prova orale consiste in domande relative alla teoria e alle dimostrazioni presentate nelle lezioni. Non ci sono domande che richiedono lo svolgimento di esercizi. Durante la prova orale ci sarà una discussione degli errori della prova scritta.Written examination: exercises. Grade: 30-ths To be admitted to the oral examination it is required a grade 15 or more. Oral examination: questions about the contents and the proofs seen during the lessons of the course. No exercises requested. There will be a discussion about the mistakes done in the written examination.- 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 planarità, grafi planari e poliedri, omeomorfismo, caratterizzazione dei grafi planari.
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.
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.
Grafi: cartella Dropbox che il docente rende disponibile su richiesta dello studente.
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
Giorni Ore Aula - Oggetto:
Note
- Oggetto: