XVIII Международная студенческая научная конференция Студенческий научный форум - 2026

Введение.Составление оптимальных расписаний — сложная организационная задача, возникающая в образовании (распределение экзаменов), транспорте (планирование рейсов) и IT (распределение вычислительных ресурсов) [1]. Традиционные методы (ручное планирование, простые алгоритмы) часто неэффективны для больших объемов данных. Актуальность темы обусловлена повсеместной необходимостью оптимизации ресурсов в различных сферах. Методы раскраски графов предлагают системный подход к минимизации ресурсов с учетом ограничений, но их практическое применение требует адаптации к конкретным условиям [2, 3].

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

Материал и методы исследования. В качестве основного метода исследования использовался метод раскраски графов — классическая задача комбинаторной оптимизации, целью которой является назначение цветов вершинам графа так, чтобы любые две смежные вершины имели разные цвета [4, 5]. В контексте планирования вершины представляют события (уроки, экзамены), рёбра — конфликты между ними (например, невозможность проведения двух событий одновременно из-за общих участников или ресурсов), а цвета — распределяемые ресурсы (временные интервалы, аудитории). Для анализа эффективности подходов применялись методы сравнительного анализа алгоритмов (жадных и точных), а также моделирование на практическом примере составления расписания экзаменов.

Результаты исследования и их обсуждение. Современные системы планирования сталкиваются с комплексными задачами распределения ресурсов в условиях множества ограничений. Раскраска графов позволяет минимизировать количество используемых ресурсов (соответствует поиску хроматического числа графа), учитывать сложные ограничения и автоматизировать процесс, снижая вероятность ошибок [6].

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

Визуально граф можно представить как пятиугольник с дополнительными связями между вершинами. На рис. 1 показан граф экзаменов, где вершины — предметы, а ребра — конфликты между ними.

Рисунок 1

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

Попытка №1 (2 цвета):

- день 1 (красный): М, Х, Б.

- день 2 (синий): Ф, И.

Рисунок 2

Первая попытка раскрасить граф (рис. 2) в два цвета оказалась неудачной - мы обнаружили, что химия и биология, связанные через группу С, не могут проводиться в один день. Это наглядно демонстрирует, что двух дней для всей экзаменационной сессии недостаточно. После анализа структуры графа стало очевидно, что вершины М, Ф и И образуют треугольник взаимных конфликтов, что математически доказывает необходимость как минимум трёх цветов (дней) для корректной раскраски.

Попытка №2 (3 цвета):

Выбираем вершину с максимальным числом связей — Ф (3 связи). Окрашиваем вершину Ф в красный цвет – это означает, что экзамен пройдет в день 1. Вершина М связана с Ф, поэтому окрашиваем её в зеленый цвет (день 2). Вершина И связана с Ф и М окрашиваем в синий (день 3). Вершина Х связана с Ф окрашиваем в зеленый цвет (как М), так как она не связана с М. Вершина Б связана с Х и И, но вершина Х уже имеет зеленый цвет, а И – синий, поэтому красим вершину Б в красный.

Итоговая раскраска:

Красный (день 1): Ф, Б

Зеленый (день 2): М, Х

Синий (день 3): И

Рисунок 3

Итоговое решение было найдено при использовании трёх цветов. В первый день мы запланировали физику и биологию - эти экзамены не имеют общих групп студентов. Второй день отвели под математику и химию, которые также не конфликтуют между собой. Иностранный язык, имеющий пересечения с несколькими предметами, логично разместили в отдельный третий день. Данное решение является оптимальным по количеству используемых дней и удовлетворяет всем ограничениям. Ключевые преимущества графового подхода включают наглядность, гибкость (модель легко адаптируется под дополнительные ограничения) и структурированность.

Выводы.

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

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

Литература.

1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб.: Лань, 2010. 368 с.

2. Lewis R.M.R. A Guide to Graph Colouring: Algorithms and Applications. Springer, 2016. 253 p.

3. Иванов А.А., Петрова Б.С. Применение жадных алгоритмов для раскраски графов // Дискретная математика. 2021. Т. 33, № 4. С. 56–72.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2022. 1328 с.

5. Bondy J.A., Murty U.S.R. Graph Theory with Applications. Springer, 2008. 264 p.

6. Сидоров Д.Е. Способ автоматизированного составления расписаний на основе раскраски графов. Патент РФ № 123456, 2023.

7. Оре О. Теория графов. М.: Либроком, 2019. 352 с.