• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта
Бакалавриат 2020/2021

## Прикладная теория графов

Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 4-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для всех кампусов НИУ ВШЭ
Преподаватели: Боду Лоран
Язык: английский
Кредиты: 5

### 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 Introduction
Introduction 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 algorithms
A 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, reachability
A highly connected network is a robust network. In this chapter we see connectivity issues in graphs.
• Flows in networks
How 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 graphs
The chromatic number of a graph is much harder to compute than its connectivity. We discuss this large field.
• Large graphs and social networks
A glimpse at metrics and method used for approaching large graphs.

#### Assessment Elements

• Homeworks
At least 2 homeworks.
• Exam

#### Interim Assessment

• Interim assessment (2 module)
0.7 * Exam + 0.3 * Homeworks

#### Recommended Core Bibliography

• Diestel R. Graph Theory. – Springer, 2017. – 428 pp.