Bachelor 2022/2023

Applied Graph Theory

Type: Elective course (Applied Mathematics and Information Science)

Area of studies: Applied Mathematics and Information Science

Delivered by: School of Data Analysis and Artificial Intelligence

Where: Faculty of Computer Science

When: 4 year, 1, 2 module

Mode of studies: offline

Open to: students of one campus

Instructors: Тhomas Clement Fernique

Language: English

ECTS credits: 5

Contact hours: 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.