СПЕЦКУРС «ЧИСЛО НЕЗАВИСИМОСТИ И ХРОМАТИЧЕСКОЕ ЧИСЛО ГРАФА»
Максим Дидин
Автор спецкурса
Член жюри финала ВсОШ по математике
Автор задач различных этапов ВсОШ по математике
Победитель международной олимпиады по математике IMO
Преподаватель математического анализа в МФТИ
Максим Дидин
Автор спецкурса
Член жюри финала ВсОШ по математике
Автор задач различных этапов ВсОШ по математике
Победитель международной олимпиады по математике IMO
Преподаватель математического анализа на Физтехе
Число независимости и хроматическое число возникают во многих задачах теории графов. С ними связано много труднейших задач и гипотез (теорема о четырёх красках, задача о хроматическом числе плоского графа, все рёбра которого имеют длину 1 и др.)
Известно, что число независимости и хроматическое число дружат со степенями вершин графа и числом его рёбер, красивые точные оценки дают, например, теорема Турана и теорема Брукса.
Программа спецкурса:
1. Теорема Турана как серия линейных оценок на число вершин n, число рёбер m и число независимости а графа. Множество возможных графов в координатах, его выпуклость. Подход через удаление вершины с соседями для доказательства линейных оценок
2. Оценки хроматического числа через число независимости и максимальную степень вершины. Теорема Брукса
ГРАФИК ОБУЧЕНИЯ НА СПЕЦКУРСЕ
19 августа
Лекция в записи + листик с упражнениями и задачами.
20 августа
Самостоятельное решение задач.
21 августа
Разбор упражнений и задач онлайн в прямом эфире.
22 августа
Лекция в записи + листик с упражнениями и задачами.
23 августа
Самостоятельное решение задач.
24 августа
Самостоятельное решение задач.
25 августа
Дорешивание и финальный онлайн разбор в прямом эфире.
ГРАФИК ОБУЧЕНИЯ НА СПЕЦКУРСЕ
19 августа
Лекция в записи + листик с упражнениями и задачами.
20 августа
Самостоятельное решение задач.
21 августа
Разбор упражнений и задач онлайн в прямом эфире.
22 августа
Лекция в записи + листик с упражнениями и задачами.
23 августа
Самостоятельное решение задач.
24 августа
Самостоятельное решение задач.
25 августа
Дорешивание и финальный онлайн разбор в прямом эфире.