Сфера применения теории графов довольно широка. Она позволяет решать такие практические задачи, как поиск кратчайшего пути, раскраска карт, сборка микросхем, организация ссылок сети 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).
Создание файла происходит пошагово:
- Ввод общей информации - списков всех групп, преподавателей, предметов, длительности занятий и комментария к расписанию.
- Установка ассоциаций между группами и предметами. На данном шаге пользователю предлагается установить, какие предметы будут проводиться в той или иной группе.
- Установка ассоциаций между преподавателями и предметами. Аналогично предыдущему шагу, устанавливается, какие предметы ведет каждый из преподавателей.
- Установка ограничений. На данном шаге пользователь устанавливает, какие из предметов нельзя проводить вместе.
- Сохранение файла. Данный этап является заключительным. На этом этапе пользователю предлагается сохранить полученный файл входных данных.
В данной работе были исследованы основные направления, концепции, касающиеся проблемы раскраски графов. Было рассмотрено несколько алгоритмов раскраски. В результате проведенного анализа для практической части работы был выбран вышеприведенный алгоритм. Хотя данный алгоритм является приближенным, он дает относительно точный результат при довольно низких затратах ресурсов.