Некоторые результаты современной теории графов

Аспирантура 2025/2026

Статус: Курс по выбору

Кто читает: Кафедра фундаментальной математики

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Когда читается: 2-й курс, 2 семестр

Охват аудитории: для своего кампуса

Преподаватели: Галкин Олег Евгеньевич

Язык: русский

Кредиты: 2

Дополнительные материалы в LMS Задать вопрос

Аннотация

Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах

Цель освоения дисциплины

Программа курса включает изучение фундаментальных понятий, таких как вершины, рёбра, подграфы, связность, эйлеровы и гамильтоновы циклы, деревья, планарные графы, клики и хроматическое число. Особое внимание уделяется алгоритмическим аспектам, таким как методы нахождения кратчайших путей, минимального остова, максимальных потоков и паросочетаний. Рассмотреть ключевые результаты и методы современной теории графов, изучив основные понятия, алгоритмы и приложения в разных областях науки и практики.

Планируемые результаты обучения

Знает основные определения и алгоритмы на графах.
- Знать и уметь применять теорию асимптотического анализа - Знать и уметь реализовывать основные алгоритмы сортировки и поиска порядковой статистики. - Знать и уметь реализовывать основные деревья поиска - Освоить базовые понятия теории графов, уметь решать задачи на эту тему - Знать и уметь реализовывать основные алгоритмы поиска кратчайшего пути в графе - Знать и уметь реализовывать основные алгоритмы вычислительной геометрии решать задачи на эту тему
Получть представление о следующих понятиях степень вершины, путь, цикл; лемма о рукопожатиях; Эйлеров путь, задача о мостах в Кёнигсберге; связность и связные компоненты; полные графы, клики, независимые множества; раскраски графов, двудольные графы, критерий двудольности; паросочетания и вершинные покрытия.