Введение к работе
I. Актуальность темы. Исследованию задач раскрас л в дискретної! математико уделяется большое внимание. Это обусловлено тесной связью проблемы раскраски с рядом важных прикладных задач, включая, например, составлг че оптимального расписание, минимизацию памяти программ, минимизацию числа процессоров в распределенных параллельных вычислениях и ряд других. Большая взаимссачзь существует меаду задачами теории расписаний и задачами раскрасок, как вершинних, так и реберных.. Например, задача составления олтм/.алыюгб 'расписания экзаменационной сессии сводится к задаче о хроматическом число графа. К задаче о наховде-нии хроматического класса сведется задача составления расписа-ний спортивных соревнований. В связи со сказанным исследование хроматических параметров грзра имеет вачюе значонио для теории расписаний. Изучению хроматического числа и хроматического класса посвяшени известно работы О.В.Бородина, Р.Л.Брукса, В.Г.Визинга, П.Катлкна, А,Д.Кор>зуиова, А.В.Косточки, Л.С.Мельникова, Н.Н.Коааиа, Р.Уилсона, И.Хольера, К.Э.С'енпона, П.Эрдо-па.
Особенно много задач теории расписаний сводится к задачам существования и построения реберных раскрасок ешциального вида в двудольных мультиграфах.
Например, Д.Фолкман и Д.Фалкерсон рассмотрели задачу о правильной расіфаске ребер двудольного мультиграфа в *L цветов, при которой в I.-ни цвет окрашено ,<.. ребер, 1= і ,...,Х . Эта задача соответствует задаче построения учебного расписания на X часов, где на і-ом часе имеется ( аудиторий, L -
=М,...,Т Некоторые достаточные условия существования требуемой раскраски найдены А.С.Асратяном к Д.де Верра.
С.Ивы, А .Итак, А.Шамир рассмотрели задачу о существовании
учебного расписания, учитыващзго индивидуальные пожелания пре
подавателей, и показали, что в общем случае эта задача -/fj-
-цолна. Ее графовым 'аналогом является задача правильной раскра
ски ребер двудольного ыультигрэфа G- в *%. цботов, где кавдой
вершино одной доли G- заранее предписано шояоство цветов, в
которые шгуї быть окрашены ребра, ищздентнне этой вершше.
Отметим,' что к частному случаю отой задачи сводится известная
задача Т.Эваноа о дополнении частичного латинского квадрата до
полного, решенная Л.Д.Андерсеном и А.Д.Хклтоном и, независимо,
Р.М.Декерелдом. ,
Д.де Верра исследовал задачу существования и построения такой реберной раскраски двудольного кулътигргфа, при которой числа ребер разных цветов, инцидентных кавдой вершине, отличаются не более чем на і . Было показано, что для любого двудольного ыультмгра^а 1^ и любого натурального К ребра G- можно окрасить в К цветов требуемым образом. Эта задача соот- ветствует задаче равномерного распределения нагрузки преподавателей и групп по дням недели;
Одним из аспектов в задачах теории расписаний является составление расписаний без прерываний. Обычно расписанием ^ез прерываний называется расписание, при котором каадое требование выполняется одним прибором непрерывно во врэмени. Существует, і дако, ряд важных малоизученных задач в теории расписаний (как, нацрш&р, составление пжольных расписаний без "окон", где каздая учебная группа и (идя) каждый преподЕхахель проводя* аа-
нятия непрерывно во времени), которые выходят за рамки такого понимания расписаний без прерываний. Изучение задач р :красок графой, соответствующих задачам существования и построения расписаний без "окон", может быть полезным как для теории расписа-ний, таї: к для выявления новых хроматических свойств графой.
-
Додъ работы. Исследование задач раскрасок, являющихся грофовьмя аналогами задач о существовании и построении "безоконных" расписаний и некоторых расписаний с предико аниякн.
-
Научная новизна. Исследованы задачи существования и построения правильних реберных раскрасок мультиграфов в цвета
1 ,...,"fc > и?11 вторых робра, инцидентные вершинам мухьтиграфа, окрашены в последовательные цвета, и для каждого L , i L &"fc і существует ребро цвета L . Такая раскраска называется интервальной 1;-раскраской. В случав двудольного иультиграфа эта задача является графовым аналогом задачи составления учебных расписаний без "окон"'. (Частино случал раскрасок введенного типа рассматривали А.С.Асратян, Й.Каро и Д.Шзнхейм.)
Найдено нообходишо условие существования гагорвальной ра-. окраски произвольного цультигрсфа: равенство ^статического класса максимальной степени верная!. Как следствие получено, что для регулярного rpaja G* проблема определения того, имеет ли Q- кнтервальнуе раскраску или нет, является S4S-полной.
Найдены верхние оценки для числа цветов п интервальных раскрасках графов некоторых классов. Например, доказано, что число цветов в интервальной раскраске двудольного графа меньше числа его вершин.
Показано, что полные двудольные графы и деревья интерваль-по окраспваоки. Найдены все значения "С , для которых сущест-
вует интервальная т-раскраска графов этих классов.
Получено достаточное условие, при котором лахЗуэ интервальную раскраску полного двудольного графаК^ модно достроить до интервальной раскрьски ладного двудольного графаК
Рассмотрены такав некоторые задачи, соответствувдие задача! о существовании и построении расписаний с прадшюанЕямп. Дія некоторых из втих з здач показана нх чгЛР-кслнота, для одной'предложен полиномиальный аягориты решения.
-
Научная к„практическая ценность. Работа шеет теоретическую направленность, Полученные результаты выявляют ношо специфичеекче хроматические свойства графов, а также могут быть использована в теории расписаний, в частности, при построении "безоконных" расписаний и некоторых расписаний с предписаниями,
-
Апробация ті^ботн. Результаты, представленные в диссертации-, били доложена в Институте математики СО АН СССР, Вычислительном центре АН Арм.ССР й ЕГУ,- Ереванском государственном университете, на VUi Всесоюзной! конференции по проблемам теоретической кибернетики в 1988 году в г.Горьком, Советско-германском рабочем семинаре по дискретной математике в 1989 году в Г.Ереване.
-
Публикации. По теме диссертации опубликовано 5 печатных работ.
? Структура и объем работы. Диссертация изложена к т. 103 страницах машинописного текста. Состоит из введения, трех глав, содержащих 10 параграфов.