Сфера применения теории графов довольно широка. Она позволяет решать такие практические задачи, как поиск кратчайшего пути, раскраска карт, сборка микросхем, организация ссылок сети Internet, составление расписаний, эффективное распределение ресурсов и т.д.
Пример составления расписания
Пусть необходимо составить учебное расписание для учебно-компьютерного центра. При этом должна быть известна некоторая информация о группах, для которых проводятся занятия; преподавателях, которые ведут эти занятия, а также о некоторых ограничениях, накладываемых, к примеру, наличием свободных аудитории.
В учебном центре необходимо провести занятия по «Пользователь ПК», «Программирование», «Пользователь 1С», «Компьютерная графика» и «Настройка компьютера» в группах А, В, С. Занятия проводятся преподавателями K, L, M.
Каждое занятие проводится в течение двух часов, включая перерывы. В центре имеются три аудитории, которые вмещают лишь одну из групп. Для занятий по физике и химии оборудована одна из этих аудиторий. Составим расписание занятий для данного случая.
Составим граф, вершинами которого являются занятия. Вершины соединим ребром, в случае, если соответствующие занятия нельзя проводить одновременно (занятия, проводятся в одной аудитории или одним преподавателям и т.д.), тогда составление расписание сводится к нахождению правильной раскраски полученного графа минимальным количеством цветом при условии, что количество вершин, окрашенных в один цвет, не будет превосходить количества аудиторий.
Сформированный граф будет выглядеть следующим образом (рис. 1а), а соответствующий ему раскрашенный граф будет иметь следующий вид (рис. 1б):
а) б)
Рис. 1. а) сформированный граф, б) раскрашенный граф
Исходя из найденной раскраски, можно построить расписание, которое будет соответствовать поставленной заданию (табл. 1):
Таблица 1.
|
|
A |
B |
C |
|
08:00 |
Программирование |
Компьютерная графика |
|
|
10:00 |
Компьютерная графика |
|
Программирование |
|
12:00 |
Настройка компьютера |
Пользователь ПК |
|
|
14:00 |
Пользователь ПК |
Пользователь 1С |
Компьютерная графика |
|
16:00 |
|
|
Настройка компьютера |
Программа DemoGraph
Практическая часть данной работы представляет собой разработку программного модуля, способного составлять учебные расписания. В итоге была разработана программа DemoGraph, с помощью которой производится составление расписания на основе введенных данных, визуализация данного процесса и сохранение полученных результатов.
Данная программа включает в себя два модуля:
- модуль DemoGraph (рис. 2) обеспечивает управление, визуализацию и сохранении;
- модуль IniCreator (рис. 3)позволяет создавать файлы входных данных.
|
|
|
|
Рис. 2. Модуль DemoGraph |
Рис. 3. Модуль INICreator |
Работа с программой проходит в три этапа:
- Загрузка специального конфигурационного файла *.ini с помощью кнопки «Открыть» или пункта меню ФайлàОткрыть (Ctrl-O). При этом согласно информации, содержащейся в файле, сформируется граф;
- Раскраска графа осуществляется с помощью кнопки «Раскрасить»
- Сохранение составленного расписания осуществляется с помощью кнопки «Сохранить» или пункта меню ФайлàСохранить (Ctrl-S). Программа на основе раскрашенного графа создаст расписание и сохранит его в виде таблице в указанном файле.
Как было сказано выше, созданию расписания предшествует загрузка входной информации, содержащейся в специальном файле с фиксированной структурой. Для создания таких файлов был разработан модуль INICreator. Запуск данного модуля возможен из окна программы с помощью кнопки «Редактор» либо из папки с программой (файл INICreator.exe).
Создание файла происходит пошагово:
- Ввод общей информации - списков всех групп, преподавателей, предметов, длительности занятий и комментария к расписанию.
- Установка ассоциаций между группами и предметами. На данном шаге пользователю предлагается установить, какие предметы будут проводиться в той или иной группе.
- Установка ассоциаций между преподавателями и предметами. Аналогично предыдущему шагу, устанавливается, какие предметы ведет каждый из преподавателей.
- Установка ограничений. На данном шаге пользователь устанавливает, какие из предметов нельзя проводить вместе.
- Сохранение файла. Данный этап является заключительным. На этом этапе пользователю предлагается сохранить полученный файл входных данных.
В данной работе были исследованы основные направления, концепции, касающиеся проблемы раскраски графов. Было рассмотрено несколько алгоритмов раскраски. В результате проведенного анализа для практической части работы был выбран вышеприведенный алгоритм. Хотя данный алгоритм является приближенным, он дает относительно точный результат при довольно низких затратах ресурсов.
Библиографическая ссылка
Зимин С.Н. СОСТАВЛЕНИЕ УЧЕБНОГО РАСПИСАНИЯ, ИСПОЛЬЗУЯ ТЕОРИЮ ГРАФОВ // Современные наукоемкие технологии. – 2007. – № 11. – С. 89-90;URL: https://top-technologies.ru/ru/article/view?id=25634 (дата обращения: 21.11.2024).