Как оптимально составлять расписания с помощью раскрасок графов?

Знакомы с правильными раскрасками графов? Существуют и много других видов раскрасок. Мы рассказываем про дефектные раскраски — мощный инструмент для решения задач составления расписаний. В статье представлены результаты работы команды в рамках Большой математической мастерской в НГУ.

Что мы сделаем в статье:
⠀⠀⠀— Объясним связь между двумя задачами: задачи раскраски графов и задачи составления расписания.
⠀⠀⠀— Рассмотрим как вершинные, так и реберные раскраски.
⠀⠀⠀— Укажем как жадные, так и точные алгоритмы решения задачи.
⠀⠀⠀— Расскажем некоторые важные свойства раскрасок.
⠀⠀⠀— Дадим оценки хроматическим числам и индексам.