Продвинутые графы

Ключевые вопросы, затрагиваемые в курсе:

• фундаментальные понятия, законы, теории случайных графов;
• современные проблемы соответствующих разделов случайных графов;
• понятия, аксиомы, методы доказательств и доказательства основных теорем в разделах, входящих в базовую часть цикл;
• основные свойства соответствующих математических объектов;
• аналитические и численные подходы и методы для решения типовых прикладных задач случайных графов

Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.

Студентам МФТИ для получения бесплатного доступа к тестовым заданиям и экзамену необходимо написать на openedu@mipt.ru письмо с указанием названия курса, логина на openedu, и скриншотом личного кабинета, на котором виден статус обучения.

Курс состоит из 13 учебных недель. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами.

Программа:

1. Обходы графов в ширину и в глубину. Дерево обхода в ширину и в глубину. Фундаментальные системы циклов
2. Потоки в сетях: теорема Форда-Фалкерсона о существовании потока, величина которого равна пропускной способности минимального разреза
3. Паросочетания. Теорема Холла в терминах паросочетаний, вывод из теоремы Форда-Фалкерсона. Системы различных представителей
4. k-связность — вершинная и рёберная. Теорема Менгера об эквивалентных определениях k-связности. Вывод теоремы Менгера из теоремы Форда-Фалкерсона. Элементарные свойства k-связных графов. Конструирование k-связных графов из имеющихся. Свойства циклов в двусвязных графах. Циклы в k-связных графах
5. Декомпозиция графов на двусвязные компоненты: BC-деревья (деревья блоков и точек сочленения)
6. Раскраски графов. Теорема Брукса. Усиления теоремы Брукса (без доказательства)
7. Чередующиеся цепочки. Связь с теоремой Холла. Теорема Кёнига
8. Теоремы Визинга о хроматических раскрасках графов и мультиграфов
9. Экстремальные задачи теории графов. Теорема Турана. Теорема Эрдёша-Стоуна-Шимоновича
10. Теоремы Эрдёша о количестве клик при ограничении на размер клики.
11. Списочные раскраски. Определения. Примеры расхождения обычного и списочного хроматического числа
12. Верхняя оценка списочного хроматического числа через обычное
13. Нижняя оценка списочного хроматического числа через минимальную степень вершин
14. Раскраски графов, укладываемых на поверхностях
15. Теорема Войгт
16. Теорема Томассена
17. Графы с большим хроматическим и малым кликовым числом. Конструкция Зыкова-Мыцельского. Теорема Эрдёша
18. Плоские триангуляции. Трёхсвязность триангуляций
19. Границы граней двусвязных графов и трёхсвязных графов. Теорема Татта и её следствия
20. Прямолинейные укладки: теорема Вагнера-Фари, теорема Татта о барицентрической укладке (без доказательства)
21. Минорно-замкнутые классы графов. Теорема Сеймура-Робертсона (без доказательства)
22. Гамильтоновы циклы. Теоремa Хватала-Эрдёша о достаточных услоовиях гамильтоновости
23. Теоремa Асратяна-Хачатряна
24. Гамильтоновость числовых последовательностей
25. Соотношения между гамильтоновостью и другими параметрами графов

Образовательные результаты:
знать: 
• фундаментальные понятия, законы, теории случайных графов;
• современные проблемы соответствующих разделов случайных графов;
• понятия, аксиомы, методы доказательств и доказательства основных теорем в разделах, входящих в базовую часть цикл;
• основные свойства соответствующих математических объектов;
• аналитические и численные подходы и методы для решения типовых прикладных задач случайных графов
уметь:
• применять различные методы теории графов для решения задач
• анализировать свойства графов и применять их в различных областях науки и техники
• работать с продвинутыми алгоритмами теории графов
• проводить самостоятельные исследования в области теории графов и представлять их результаты