Graph Theory
A.Y. 2019/2020
Learning objectives
Graphs are fundamental mathematical structures used to model pairwise relations between objects. This course covers some basic concepts of graph theory including cycles, matchings, colorings, connectivity, and extremal graphs. The second part of the course introduces some more advanced topics, such as random graphs and spectral graph theory, that have recently had a remarkable impact on computer science.
Expected learning outcomes
Upon completion of the course, students will be able to: (1) Prove the main theorems of structural graph theory; (2) understand the fundamental properties of some families of random graphs; (3) describe the main spectral quantities related to graphs and show how they can be used in algorithms. These objectives will be assessed via an oral discussion whose evaluation will determine the final grade.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
The goal of the course is to introduce graph theory with an emphasis on its algorithmic and probabilistic aspects.
1. Fundamental concepts
2. Basic results on trees and cycles
3. Matchings
4. Connectivity
5. Planar graphs
6. Extremal graph theory
7. Random graphs
8. Spectral graph theory
9. Spectral clustering
1. Fundamental concepts
2. Basic results on trees and cycles
3. Matchings
4. Connectivity
5. Planar graphs
6. Extremal graph theory
7. Random graphs
8. Spectral graph theory
9. Spectral clustering
Prerequisites for admission
The course requires basic knowledge in calculus, linear algebra, and statistics.
Before attending this course, students are strongly advised to take the folowing exams: Continuum mathematics, Discrete mathematics, Statistics and data analysis.
Before attending this course, students are strongly advised to take the folowing exams: Continuum mathematics, Discrete mathematics, Statistics and data analysis.
Teaching methods
Lectures.
Teaching Resources
The main reference are the lecture notes available through the link ncesa-bianchitg.ariel.ctu.unimi.it/
A further reference is the textbook: Reinhard Diestel, "Graph Theory", Springer Verlag, 2017.
A further reference is the textbook: Reinhard Diestel, "Graph Theory", Springer Verlag, 2017.
Assessment methods and Criteria
The exam is an oral discussion concerning the topics taught in the course, including formal definitions and mathematical proofs. The grade summarizes the level of understanding of the course topics, the clarity of exposition, and the language skills.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cesa Bianchi Nicolo' Antonio
Shifts:
-
Professor:
Cesa Bianchi Nicolo' AntonioProfessor(s)