Бакалавриат
2019/2020
Прикладная теория графов
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
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 what is GT and where it can be applied.
- Understand and apply results on trees.
- Understand and apply results on connectivity.
- Understand and apply results on flows.
- Understand results about colouring of graphs.
- Understand and apply results on Large Graphs.
Course Contents
- Graph Theory an IntroductionIntroduction to the basic concepts of a graph, notations, and famous families of graphs. Several methods of storing a graph in computer's memory are presented.
- Trees, and search algorithmsA core concept of a graph is the notion of spanning trees. They can be seen as a skeleton and appear everywhere. Different ways to build them yield trees with dierent properties. Chosing the right tree is important.
- Connectivity, reachabilityA highly connected network is a robust network. In this chapter we see connectivity issues in graphs.
- Flows in networksHow to efficiently convey things in a network with capacities on the arcs/edges? This is our main question in this chapter. We see the algorithm of Ford-Fulkerson, the dual problem of minimum cut, and their applications.
- Hard problems: colorings of graphsThe chromatic number of a graph is much harder to compute than its connectivity. We discuss this large field.
- Large graphs and social networksA glimpse at metrics and method used for approaching large graphs.