Graph Theory
A.Y. 2021/2022
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
More specific information on the delivery modes of the training activities for the academic year 2021-22 will be provided over the coming months, based on the evolution of the public health situation.
Course syllabus
The goal of the course is to introduce graph theory with an emphasis on its algorithmic and probabilistic aspects.
Basic results
Colorings, cliques, independent sets, dominating sets
Random graphs and the probabilistic method
Spectral graph analysis
Random walks on graphs
Basic results
Colorings, cliques, independent sets, dominating sets
Random graphs and the probabilistic method
Spectral graph analysis
Random walks on graphs
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
Lecture-style instruction.
Teaching Resources
The main reference are the lecture notes available through the link ncesa-bianchitg.ariel.ctu.unimi.it/
Reference textbook: Reinhard Diestel, "Graph Theory", Springer Verlag, 2017.
Reference 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.
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
Educational website(s)
Professor(s)