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

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

Направление: 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

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

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

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

Assessment Elements

  • non-blocking Homeworks
    At least 2 homeworks.
  • non-blocking Exam
Interim Assessment

Interim Assessment

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

Bibliography

Recommended Core Bibliography

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

Recommended Additional Bibliography

  • Rigo, M. Advanced graph theory and combinatorics. – John Wiley & Sons, 2016. – 290 pp.