Автоматика и телемеханика, № 1, 2015
© 2015 г. А.М. МАГОМЕДОВ, д-р физ.-мат. наук (magamedtagir1@yandex.ru) (Дагестанский государственный университет, Махачкала)
К ВОПРОСУ ОБ ИНТЕРВАЛЬНОЙ Д-РАСКРАСКЕ ДВУДОЛЬНЫХ ГРАФОВ1
Имеется существенный класс задач, в которых составление расписания минимальной длительности сводится к правильной раскраске двудольного графа наименьшим возможным количеством цветов, а составление расписания без простоев — к интервальной раскраске двудольного графа. Исследована сложность задачи интервальной Д-раскраски двудольного мультиграфа. Построен пример (6, 3)-бирегулярного графа, не обладающего интервальной Д-раскраской.
1. Введение
Эффективность применения методов теории графов для исследования задач о расписаниях хорошо известна. В свою очередь, исследования в области теории расписаний приводят к появлению новых методов и даже целых направлений в теории графов. Например, проблема четырех красок возникла в связи с задачами теории расписаний и разбиений [1, с. 110].
В задачах составления расписания взаимодействия объектов различной природы нередко присутствует двудольная структура. Пусть, например, требуется составить расписание обслуживания объектов множества X (деталей, классов и т.п.) в системе объектов У (станков, учителей и т.п.): каждой паре (х,у) € X х У запланировано не более одной операции, длительность каждой операции равна единице, условия частичного предшествования отсутствуют, запрещено одновременное взаимодействие одного объекта с несколькими. Исходные данные к расписанию удобно представить в виде двудольного графа С = (X, У, Е), где ребро (х,у) присутствует в множестве Е тогда и только тогда, когда объекту у запланирована операция с объектом х. (Всюду под графом понимается простой граф; если допускаются кратные ребра, применяется термин м у л ь т и г р а ф.)
Задачи построения расписания тесно связаны с задачами раскраски графов. Отметим, что интерес к задачам раскраски объясняется не только их важностью для приложений (построения и оптимизации расписаний, исследования сетей связи и др.), но и тесными связями с широким спектром ^Р-полных задач. Некоторые из них приведены в разделе 2, посвященном краткому обзору результатов о правильной и интервальной раскрасках графа.
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект 12-07-96500-р_юг_а), Гос. задания (проект 1.1923.2011) и Программы стратегического развития ФГБОУ ВПО «Дагестанский государственный университет» (проект 3).
В разделе 3 рассмотрен вопрос сложности задачи об интервальной рас-крашиваемости двудольного мультиграфа и построен пример (6,3)-бирегу-лярного графа, не обладающего интервальной 6-раскраской.
2. Интервальная раскраска графов
Определение 1. Правильной ¿-раскраской графа С = (V, Е) называется сюръекция с: Е ^ {1,..., такая, что с(ег) = c(ej) для любых смежных ребер ег, ej € Е. При этом с(е) называется цветом ребра е € Е.
Отождествляя дискретные моменты времени выполнения операций и цвета соответствующих ребер графа С, задачу составления расписания можно свести к задаче правильной раскраски графа С. Наименьшее для которого правильная ¿-раскраска графа существует, обозначается через х' (реберное хроматическое число). Задача составления расписания наименьшей длительности равносильна задаче правильной раскраски графа С = (X, У, Е) в цвета
1,...,х'.
Мощность множества вершин и наибольшую степень вершины графа будем обозначать через п и А соответственно полный граф с 3 вершинами -через К3. Известно [2], что А ^ х' ^ А + 1.
Пример 1. Для графа К3 х' = А + 1. Согласно теореме Кенига о реберной раскраске [3, с. 80] х' = А для любого двудольного графа.
В [4] доказано, что задача проверки равенства х' = А ЫР-полна даже для кубических графов.
Требование отсутствия в расписании простоев для каждого объекта с момента его «включения» и вплоть до «выключения» приводит к задаче об интервальной раскраске.
Определение 2. Под интервалом будем понимать набор последовательных целых чисел {а, а + 1,...,Ь}. Если ребро с цветом к инцидентно вершине V, говорят, что цвет к представлен в вершине V. Правильная ¿-рраскраска с графа С = (V, Е) называется интервальной в вершине V € V, если цвета, представленные в вершине V, образуют интервал, и интервальной ¿-раскраской графа С, если раскраска с интервальна в каждой вершине V € V. Если для заданного t интервальная ¿-рраскраска графа существует, то граф называется интервально ¿-раскрашиваемым. Если при каком-либо t граф интервально ¿-р'раскрашиваем, то граф называется интервально-раскрашиваемым.
Пример 2. Граф Кз не является интервально-раскрашиваемым. Любой однородный двудольный граф интервально А-раскрашиваем.
Термин «интервальная раскраска» впервые был введен в [5] в связи с задачей устранения «окон» в расписании учебных занятий (ранее для аналогичных целей в заметке [6] был предложен термин «раскраска с непрерывным спектром»). ЫР-полнота ряда задач раскраски графов доказывается сведением к ним известной ЫР-полной задачи «Составление учебного расписания» [7].
Всякий интервально-раскрашиваемый граф допускает правильную Д-рас-краску [5]. Задача об интервальной раскраске графа NP-полна [5]; более того, задача NP-полна и в случае двудольного графа [8]. Отметим, что для сведения к задаче об интервальной t-раскрашиваемости двудольного графа в [8] выбрана задача о составлении расписания «Упорядочение внутри интервалов» [1, с. 93], NP-полнота которой, в свою очередь, доказана в [1, с. 93-94] сведением к ней задачи разбиения, входящей в список шести основных NP-полных задач [1, с. 65-66]. В этой связи обратим внимание на «непосредственное» сведение задачи разбиения к задаче об интервальной раскраске двудольного мультиграфа, приведенное в Приложении.
Определение 3. Двудольный граф G = (X, Y, E) называется (а, в)-би-регулярным, если степень каждой вершины множества X равна а, степень каждой вершины множества Y равна ß.
В одной из первых работ по интервальной раскраске двудольных графов [9] указаны следующие классы интервально-раскрашиваемых двудольных графов: полные графы, графы с Д ^ 3 и (Д, 2)-бирегулярные графы с четным Д. В [10] упоминается (6,3)-бирегулярный граф G = (X, Y, E) с n = 60, не обладающий кубическим подграфом, включающим множество вершин X (такой граф не допускает интервальной 6-раскраски). При нечетном Д любой (Д, 2)-бирегулярный граф интервально (Д + 1)-раскрашиваем [11]. С привлечением компьютерных вычислений в [12] доказано, что каждый двудольный граф с n ^ 14 интервально-раскрашиваем. Двудольные графы G = (X, Y, E) с небольшими значениями Д и n, не допускающие интервальной раскраски, были построены следующими авторами: С.В. Севастьянов (Д = 21, n = 28), M. Malafiejcki (Д = 15, n = 19), A. Hertz (Д = 14, n = 23), D.deWerra (Д = 14, n = 21), P.Erdos (Д = 13, n = 27).
Замечание 1. В каждом из перечисленных примеров min {|X|, |Y|} > 3.
Задача об интервальной 4-раскрашиваемости двудольного графа G = = (X,Y,E), где
dGx = 4 Vx € X, dGy ^ 4 Vy € Y,
рассмотрена в [13] в терминах расписаний; доказана разрешимость за полиномиальное время (доказательство без труда переносится на случай произвольного двудольного графа с Д = 4). В [14] показано, что задача об интервальной Д-раскрашиваемости двудольного графа разрешима за полиномиальное время при Д ^ 4 и NP-полна при Д = 5. В [15] установлена NP-полнота задачи об интервальной Д-раскрашиваемости (6,3)-бирегулярного графа.
3. Два утверждения об интервальной Д-раскраске
3.1. Интервальная Д-раскраска двудольного мультиграфа
Определение 4. Набор всех ребер заданного двудольного мультиграфа G = (X, Y, E) с концами в вершинах xi и yj будем называть пучком и обозначать через Eij. Интервальную раскраску мультиграфа будем называть интервальной в пучке, если цвета ребер пучка различны и образуют интер-
(Условимся и в дальнейшем тексте не разделять индексы запятыми, если каждый из индексов представлен одним символом: буквой или цифрой.)
Задача об интервальной А-раскрашиваемости двудольного мультиграфа
Условие. Задан двудольный мультиграф С = (Х, У, Е), Х = {х1, х2}, ¿сХ1 = ¿сх2 = А, ¿су ^ Г А/2 ] для каждой вершины у £ У.
Вопрос. Существует ли интервальная А-раскраска мультиграфа С, интервальная в каждом пучке?
Утверждение 1. Задача об интервальной А-раскрашиваемости двудольного мультиграфа С = (X, У, Е) ЖР-полна (даже при |Х| = 2).
В [16] доказано, что если |Х| ^ 3, то для любого простого двудольного графа С = (X, У, Е) существует интервальная раскраска (см. замечание 1).
3.2. Простой (6, 3)-бирегулярный граф, не допускающий интервальной 6-раскраски
Утверждение 2. Простой (6,3)-бирегулярный граф С, полученный объединением двудольных графов = (Х1 ,У1 ,Е1) и С2 = (Х2,У2,Е2), изображенных на рис. 1 и рис. 2, не допускает интервальной 6-раскраски.
Рис. 1. Граф = (Хх,Ух, Е\).
Рис. 2. Граф = (Х2,У2,Е2).
Доказательства утверждений 1 и 2 даны в Приложении.
Замечание 2. Построение (6,3)-бирегулярного мультиграфа, не обладающего интервальной Д-раскраской, тривиально. Например, граф G = (X, Y, E), где X = (xi, ж2, ж3, ж4}, Y = {yi, множество ребер E задано списками смежности: у1(ж1,ж1,ж2,ж2,ж3,ж3), у2(ж1,ж2,ж3,ж4,ж4,ж4), не обладает интервальной 6-раскраской.
4. Заключение
Для расписания взаимодействия объектов множества двудольной природы G = (V, E) = (X, Y, E) с предписанными операциями рассмотрена проблема минимизации общей длительности расписания и индивидуальных длительностей участия в расписании каждого из объектов Vi. Более точно, рассмотрены вопросы достижимости этими длительностями своих «естественных» нижних границ (Д - для всего расписания и do Vi - для каждого объекта Vi).
Теоретико-графовая интерпретация задачи позволила выявить связи с известными задачами, некоторые из которых по своим характеристикам близки к реальным прикладным задачам составления расписания. Например, в связи с однодневным «школьным» расписанием длительности 5 или 6 (уроков) представляется уместным выделить следующие пункты:
• в [8] доказано, что задача об интервальной 5-раскрашиваемости двудольн
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.