Элементы теории графов в мировой динамике

Пример составления  расписания

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

В учебном центре необходимо провести занятия по «Введение в специальность», «Философия», «Высшая математика», «Белорусский язык» и «Иностранный язык» в группах А, В, С. Занятия проводятся преподавателями K, L, M.

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

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

Сформированный граф будет  выглядеть следующим образом (рис. 1а), а соответствующий ему раскрашенный граф будет иметь следующий вид (рис. 1б):

а)                                                                           б)

Рис. 1. а) сформированный граф, б) раскрашенный граф

Исходя из найденной раскраски, можно построить расписание, которое  будет соответствовать поставленной заданию (табл. 1):

Таблица 1.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:

1. Оре, О. Графы и их применение = Graphs and Their Uses / О. Оре; Пер.с англ. Л.И. Головиной; Под ред. И.М. Яглома. - 2-е изд.,стер. - М. : Едиториал УРСС, 2002. - 172с.
2. Зыков, А.А. Основы теории графов / А.А. Зыков. - М.:Наука, 1987. – 384 с.
3. Оре, О. Теория графов / О.Оре. – 2-е изд.— М.: Наука, Главная редакция физико-математической литературы, 1980. – 336 с.
4. Графы и архитектра [Электронный ресурс] / Применение теории графов.– Режим доступа: https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/integracionnaa-svaz. – Дата доступа: 20.10.2012