Бакалавриат
2021/2022
Прикладная теория графов
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Боду Лоран
Язык:
английский
Кредиты:
5
Контактные часы:
60
Course Syllabus
Abstract
Bondy and Murty open the first chapter of their book Graph Theory with the following sentence: “Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points.” This diagram is nothing but a representation of what is called a graph. Whether it is for logistics, optimization of processes, network analysis, communication methods or bioinformatics, most of applied mathematics make use of graph theory. In this course, we familiarize ourselves with these objects in their diversity (simple graphs, directed graphs, hypergraphs) and with the standard methods to solve standard problems as: shortest path, maximum flow/minimum cut, connectivity... We illustrate most of these staple problems with applications to real life situations.
Learning Objectives
- To give a broad overview of problems and some resolutions in Graph Theory. The aim is to provide students with sufficient knowledge for them to naturally pick the good model when facing a “real-life” problem in the future. After choosing the model, the students should be able to adapt state-of-the-art algorithms to the situation and thus provide a solution with justifications (exact algorithms, approximation algorithm, theoretical complexity of task).
Expected Learning Outcomes
- Understand and apply results on connectivity.
- Understand and apply results on flows.
- Understand and apply results on Large Graphs.
- Understand and apply results on trees.
- Understand results about colouring of graphs.
- Understand what is GT and where it can be applied.
