Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах
Цель освоения дисциплины
Программа курса включает изучение фундаментальных понятий, таких как вершины, рёбра, подграфы, связность, эйлеровы и гамильтоновы циклы, деревья, планарные графы, клики и хроматическое число. Особое внимание уделяется алгоритмическим аспектам, таким как методы нахождения кратчайших путей, минимального остова, максимальных потоков и паросочетаний.
Рассмотреть ключевые результаты и методы современной теории графов, изучив основные понятия, алгоритмы и приложения в разных областях науки и практики.
Планируемые результаты обучения
Знает основные определения и алгоритмы на графах.
- Знать и уметь применять теорию асимптотического анализа
- Знать и уметь реализовывать основные алгоритмы сортировки и поиска порядковой статистики.
- Знать и уметь реализовывать основные деревья поиска
- Освоить базовые понятия теории графов, уметь решать задачи на эту тему
- Знать и уметь реализовывать основные алгоритмы поиска кратчайшего пути в графе
- Знать и уметь реализовывать основные алгоритмы вычислительной геометрии решать задачи на эту тему
Получть представление о следующих понятиях степень вершины, путь, цикл; лемма о рукопожатиях; Эйлеров путь, задача о мостах в Кёнигсберге; связность и связные компоненты; полные графы, клики, независимые множества; раскраски графов, двудольные графы, критерий двудольности; паросочетания и вершинные покрытия.
Содержание учебной дисциплины
Основы теории графов
Деревья и ориентированные графы
Элементы контроля
In-class assignment
Oral interview
Промежуточная аттестация
2025/2026 2nd semester
0.5 * In-class assignment + 0.5 * Oral interview
Список литературы
Рекомендуемая основная литература
Бинарные отношения, графы и коллективные решения, учебное пособие, 2-е изд., перераб. и доп., 341 с., Алескеров, Ф. Т., Хабина, Э. Л., Шварц, Д. А., 2017
Лекции по теории графов, учебное пособие, 4-е изд., 383 с., Емеличев, В. А., Мельников, О. И., Сарванов, В. И., Тышкевич, Р. И., 2015
Теория графов, Карпов, Д. В., 2022
Рекомендуемая дополнительная литература
Аналитическая теория циркулянтных графов и ее приложения к комбинаторному анализу : автореф. дис. ... канд. физ.-мат. наук : 1.1.1, Грюнвальд, Л. А., 2025
Комбинаторика и теория графов : учеб. пособие, Носов, В. А., 2000
Преподаватель
Галкин Олег Евгеньевич
Программа дисциплины
Аннотация
Цель освоения дисциплины
Планируемые результаты обучения
Содержание учебной дисциплины
Элементы контроля
Промежуточная аттестация
Список литературы
Рекомендуемая основная литература
Рекомендуемая дополнительная литература
Авторы