Combinatorics and Graph Theory

2026/2027

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

1 year, 1 module

Instructors

Beldiev, Ivan

Maksaev, Artem

Программа дисциплины

Аннотация

Курс знакомит с фундаментальными понятиями и методами двух тесно связанных областей дискретной математики. В первой части рассматриваются основные комбинаторные принципы: правила суммы и произведения, биномиальные и полиномиальные коэффициенты, формула включений-исключений, а также метод математической индукции в его различных формах. Вторая часть посвящена теории графов — изучаются неориентированные и ориентированные графы, деревья, связность, эйлеровы циклы, раскраски и хроматический многочлен, паросочетания, вершинные покрытия и теорема Кёнига. Кроме того, курс включает введение в вероятностные методы: вероятностное пространство, условная вероятность, независимость, математическое ожидание, неравенства Маркова и Чебышёва, а также классические приложения вероятностного метода в комбинаторике, включая оценки чисел Рамсея.