Интервальные реберные раскраски графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

\

АКАДЕМИЯ НАУК СССР

ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

КАШЯН Рафаел Рубенович ШГЕЕВАЛШНЕ РЕБЕЖЫВ РАСКРАСКИ ГРАФОВ 0I.0I.C9 - математическая киборнетпка

Авгорофера!

диссертация на сопскапио ученой степени неидэдага фЕзЕко-иахомапиеских пауте

}

На правах рулошоп

УЖ 519.1

Новосибирск - 1990

Работа выполнена в Вычислительном центре Академии неук Армянской ССР и Ш.

Научный руководитель: кандидат физико-математических наук, доцент АОРАТЯН A.C.

Официальные оппоненты: доктор физико-математических наук

ШЕВЧЕНКО В.Н.

кандидат физико-математических наук КОСТОЧКА A.B.

Ведущая организация: Московский государственный

университет иш М.В.Ломоносова

Защита состоится "_" _;_ 1990 г. в_чао.

на заседании Специализированного совета К 002.23.01 в Институте ыатешдвхи СО АН СССР (530090, Новосибирск, 90, Университетский пр„, 4, Институт математики СО АН СССР).

С диссертацией можно, ознакомиться в библиотеке Института математики СО АН СССР.

Автореферат разослан "_" _• ' 1990 г.

Ученый секретарь Спедиализг овакного совета,

кандидат физвко-чаатоматичэских наук ¿^р / Ю. Л.Васильев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЦ

X. Актуальность теш. Исследованию задач раокрас в дискретной математике уделяется болыяое внимание. Это обусловлено тесной связью проблемы раскраски с рддом вшшых прикладных задач, включая, налр^.'.ер, состагдг -те оптимального расписание, минимизацию памяти программ, минимизацию 'шсла процессоров в распредоленных параллельных вычислениях и ряд других. Болъиая взаимосвязь существует меяду задача,® теории расписаний и задачами раскрасок, как вершинных, так и реберных.. Например, задача составления оптимальногорасписания экзаменационной сессии сводится к задаче о хроматическом число графа. К задаче о нахождении хроматического масса сводится задача составления расписаний спортивных соревнований. В связи со сказанным иссл^дованиэ хроматических параметров графа имеет ззггзюе значение для теории расписаний. Изучению хроматичз с ко го числа к хроматического класса посвящены, известные работы О.В.Бородша, Р.Л.Брукса, В.Г.Визинга, П.Катлкна, А.Д.Коршунова, А.В.Косточки, Л.С.Мельникова, Н.НЛ',с;хана, Р.Уилсона, И.Хольера, К.Э.К'ыпона, П.Эрде-па.

Особенно много задач теория расписаний сводится к задачам существования и построения реберных рас красок специального вида в двудольных ыулътиграфах.

Например, Д.Фолкмаи и Д.Фашзрсоп рассмотрели задачу о правильной раскраске ребер двудольного мультиграфа в X цветов, при которой в 1-ый цвет окрашено ,<..; ребер,I = Т. . Эта задача соответствует задаче построения учебного расписания на Ъ часов, где на 1-ом часе имеется _ аудиторий,

3

= •!,... Некоторые достаточные условия существования требуемой раскраски найдены А.С .Асратяном к Д.де Верра.

С.Иен, А.Итаи, А.Шжир рассмотрели задачу о существовании учебного расписания, учеткв&щвго индивидуальные пожелания препод аваз елей, и показали, что в общем случае эта задача -АГ^Р--лолна. Ее графовим аналогом являемся задача правильной раскраски ребер двудольного ыультшрафа С- в \ цветов, где кввдой Ббршино одной доли О заранее тгредписено множество цветов, в которые могут- быть окршоны ребра, инцидентные этой варишге. Отаотиь;, что к частному случаю стой задачи сводится известная задача Т.Эванса о дополнении частичного латинского квадрата до полного, решенная Л.Д.Андерсеном и А.Д.Хилтоном и, независимо, Р.М.Дашреллом.

Д.де Верра исследовал задачу существования и построения такой реберной раскраски двудольного культиграфа, при которой числа ребер разных цветов, инцидентных каждой вершине, отличаются не более чем на 1 . Бнло показано, что для любого двудольного мультмгра^а & и любого натурального К ребра & можно окрасить в К цветов требуемым образом. Эта задача соот- • ветствует задаче равномерного распределения нагрузки преподавателей и хрупа по дням недели;

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

4

нятия непрерывно во времени), которш выходят за рамки такого понимания расписаний без прерпваний. Изучение задач р ¡красок графов, соответствундих задачам существования и построения расписаний без "окон", может быть полезным как для теории расписаний, так и для выявления новых г>^магических свойств графой.

2. Поль роботы. Исследование задач раскрасок, являющихся графовыми аналогами задач о существовании и построении "безоконных" расписаний и некоторых расписаний с предписаниями,

3. Научная новизна. Исследованы задачи существования и построения правильных реберных раскрасок мультиграфоз в цвета

1,... • Щ® вторых ребра, инцидентные вершинам мулътиграфа, окрашены в последовательные цвета, и для кавдого I И ^ I , существует ребро цвета I . Токая раскраска называется интервальной -раскраской. В случае двудольного мульт штрафа эта задача является графоскм аналогом задачи составления учзбннх расписаний без "окон". (Частные случая раскрасок вьэдешог-о типа рассматривали А.С.Асратян, Й.Каро'И Д.Еенхейм.)

НаЦдено необходимое условие существования инторвальной ра~ .окраски произвольного мультигрофа: равенство хрсатического класса максимальной степени вершин. Как следствие» получено, что для регулярного графа С* проблема определения тою, имеет ли О- интервальную раскрась дли нет, является ч/Т(Р~полкой.

Найдены верхние оценки для числа постов в шторвалышх раскрасках графов некоторых классов. Например, доказано, что число цветов в интервальной раскраске двудольного графа меньше числа его вершин.

Показано, что полные двудольные графы и деревья интерваль-ио окрашиваемы. НвЯдеш все значения ^ . для которых сущест-

5

вуег интервальная "t-раскраска ipa$os этих классов.

Получено достаточное условие, прн котором любую интервальную раскраску полного двудольного графа К. ^ ^ могло достроить до интервальной раскраски полного двудольного графа К.

Рассмотрены та;кае некоторые задачи, соответствующие задачам о существовании и построении расписаний с прадтшсаишши. Для некоторых еэ отек задач показ сне их ЛУ^-полнота, для одной'предлокон полиномиальный алгоритм решения.

4. Научная и практическая пеньость. Работа имеет теоретическую направленность. Полученные результаты шявляат ноше специфические хрома-ткчзехке свойства графов, а также могут бнгъ попользованы в теории расписаний, в частности, при построении "безоконных" расписаний и некоторых расписаний с предписаниями.

5. Атпюбздшг габотц. Результаты, представленные в диссертации-, были доложены в Институте математики СО АН СССР, Вычислительном центре АН Api,«.ССР й ЕПГ, Ереванском государственном университете, на VI!! Всесоюзно® конференции по проблемам теоретической кибернетики в 1988 году в г.Горьком, Советско-германском рабочем семинаре по дискретной математике в 1989 году в г.Ереване.

6. Нтбликетгш. По теме диссертации опубликовано 5 печатных работ.

7. Структур*. и объем работы. Диссертация иэло&она кя 103 страницах машинописного текста. Состоит из введения, трех глав, содержаний 10 napaiyaJoB.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении рассмотрены некоторое задачи, шшютриругдав

5

связь задач раскрасок с задачам: теории расписаний, а также сформулированы основные результаты диссертации.

В Главе I дани основнпе опредолония и обозначения. Пусть От — СУ(Сг) , ГиСО")) " мультиграф. Степень ворши-1Ш X п О- обозначим через с( ОО • максимальную из стег"'ой вершин - через Д , хротати. ¿кий класс С- - через х'С.С~). Пусть • ¿шторшлъноц на ^ -раскраской муль-

тиграфа О- назовем правильную раскраску ребер 0- в цвета С, ,..., С^. при которой в катдш! цвет С^ , А $ & Ь , окрашено хотя бы одно ребро, и ребра, инцидентные качдой вериино

, окрашены в (^.^Скупоследоватолыпл: цветов. Непрорывной па Ь^. ^-раскраской мультиграфа С" назовем правильна раскраску ребер С" в цвета С^,-.., С ^ , при которой в качппЯ цвет С^ , 1 й I ¿"Ь , окра^но хотя бы одно ребро, и ребра, инцидентные каддой ворашю к^Рч , окрашены в цвета С1>..., Са Пусть ¡ГС^. - мю.тестпо культиграфов О- , для которих существует интервальная наУСС-") "^-раскраска, и — ^ • Лля 0г& \С обозначим через и У\А(т),

соответственно, наименьшее и наибольшее 'С , Длч которого су-цествует интервальная наЬ -раскраска 2 § I Глппн I доказана

Теорока 1.1.1. Если От 6 , то Х'чСг) Д(ч&) • Как следствие этой теоремы отмечено, что для регулярного графа (у проблема определения: Сг £ ТС или йХ , является и (Р-полной.

В § 2 Главк 1 найдены некоторые неравенства о параметраа графов класса

, Основные результата параграфа следущае: 7

Теорема 1.2.1. Пусть О -связный граф с 1Е(.Сг)\ <> А •

если & е Ги , то \ATCQ ^ -

Теорема 1.2.2. Для любого р> о существует 1раф О таКОЙ, что а е а и

Теорема 1.2.3. Пусть С- - связный г^аф без треугольников. Если 0- е Ж. , то \Д/Г(.0г>) \ЛГС&)\ - А.

Следствие 1.2.1. Если О- - связный двудольный граф, и

то

Б § 3 Главы I исследованы интервальные раскраски полных двудольных графов. Полный двудольный граф с т. вершинами в одной доле, Ю, вершинами в другой, обозначаем через «

Наибольший общий делитель натуральных чисел ууи и VI обозначаем через »УХ}. Доказана

Теорема 1.3.1. Для любых натуральных УП, и П.

з/Ч^СК^А ,

4) ссли^СК^^-Ь^АГСК^Д .

Следствие 1.3.1. Если , 1, то К^ „.^ тогда

и только тогда, ковда 1и — УП + ГС—Л .

В § 4 Главы I исследованы интервальные раскраски деревьев.

Пусть дерево ДГ(3->) —Через обоэнаЧ1Ш «е1ш» соединяющую вершины и ъ.

через"V \_( , - множество вершин и мнояе-

^ I. ¿г . и ¿г

¿Г

^^¿жх и- и _ итлигл^птгч тадтитти' т.т

ство ребер этой цепи, соответственно, Л^и^ф.^гЬ^б^ * цепи Л ^ < 14 $ , 4 <• > £ , введем обозначение

Доказана

Тс Л.4.1. Пусть еО - дерево. Тогда: 1)2)61(1,

4) если »V(ДУ) < "Ь « (.£>) . то .

Глава 2 посвягдена задаче достроения штерваташх раскрасок полных двудольных графов.

В § I ГЬгавы 2 сформулирована

Задача достроен и я и горвалыапс раскрасок полных двудольных графов. Каким условиям должны удовлетворять целые неотрицательные числа т.' , п,' , чтобы произвольную ин~ тервальнто наУ(К ) {"-раскраску полного двудольного 1рафа ¡ч^ л мояно било достроить до интервальной на "У( К . Л "Ъ -раокпаски полного двудольного графа К I / для какого-либо с я ?

Для нахождения достаточного условия достроения интервальных раскрасок полных двудольных графов исследована структура этих раокрасс:. Доказана

Теорема 2.2.5. Пуоть (Г = <ГСгл. .л.1), 8 = — . Тоэда

(Г

при любой интервальной ^ ) раскраске графК^^

можно разбить на Ъ полных двудольных подграфов К^ ^,... >

к " , так что К^* - окрашен иптервально на"^/\К__^,

«ГО' «г, иг чг,<г •

Достаточное условие для достроения интервальных раскрасок полных двудольных графов дает

Теорема 2.2.6. Еслисг(т/а},^<г(.т..Ух), где

цолие неотрицательные числа, то лпбую интервальную на \Г(К ^ "^-раскраску полного двудольного графа К ^ можно достроить до интервальной ^ "

-раскрлски ^ О полного двудольного графа К ^^^ .

В Главе 3 исследованы реберные раскраски специального типа и приведены некоторые применения полученных результатов.

В §1 Главы 3 исследованы односторонне-интервальные5. раскраски двудольных мультпгра&ов.

Пусть 0"= - двудольный мультиграф.

Обозначим через 00 и, соответственно, нанке-ньиее и наибольпее "Ь > для которого существует интервальная на\^С(т} 1с-раскраска 0- . Очсвадю,\^/л(Ху)=• Доказ она

Теорема 3.1.1. ЕусгьО двудоль-

ный ыультЕграф. Тогда для любого "Ь , ^(^сг^ ^¡¡¿Л/ч/дССг^) . существует интервальная наХ/^СО") "X-раскрюка ыультиграфа

а.

В § 2 Главы 3 исследуется сложность некоторых задач о существовали! в двудольных графах раскрасок с предписаниями. В частности, доказана ^Р-полнота следующих проблем.

Проблема.

Вход. Двудольный греф С Л&Сг) )) с

Свойство. Существует непрерывная -раскраска С- •

Проблема.

Вход. ДвудолышЗ чрет ,ЧХу>).. ЕССг^ с

10

- ь и целые ,

= \ECG-M.

Свойство. Существует правильная рас"раска ребер G в Цвета \, 2., Ъ , при которой в цвет L окрашено 'Д. . ро-бор, la з .

В § 3 Главы 3 рассмотрена следунщ т задана о существовании и построении двудольного мультиграфа с предписанной раскраской. Даны:

1. Множества К и У вершин: Х = \ ,

2. Множество С цветов: С.= ^»• • • >

3. Дяя каядоЯ вершшш v ç X. U 'У Л51™ целые неотрицательные числа ta (.v") и

HCv^WCv/UHCvV

4. Для каддой вэршкаыv Ç.X.U К2®111 ТРП подкноаестЕа ТА(v), > Тъ(у) цветов, где для L - ,1

5. Дгга каждой пары (к , , где KÇ.X. , . дани три подаможестваТЧС*»^ .T^x^'J) ,Т\(х,цветов, дляЫдз. ТЧСхС,ТЧ(«^))ПТЧСк,^= -ф при^сс-^з,

Твебуется выяснить, оудоствует ли двудольный мультиграф

G = C4CG), . ECO» с X (G) - X,- ^ .

тлеющий правильную pe6epiryio раскраску в цвета шояоетва С . гак что

I) для наядой вершина vev(g) ci Cv) $

II

2) для катдой вершины V е Л/СС-") к каздого а)кеТЛСу> I существует ребро цвета К , инцидентное V ,

, может существовать робро квота К , инцидентное V ,

. из существует ребра цвета К. , инцидентного

V ;

3) для каждой пари (к , где > и калдого-

ггл Л

а)КбТ ((х,^.)) , существует ребро цвета К , соединялцое вершины х и у, ,

б) КС ТЧ(х . монет существовать ребро цвета и. созде~ няыцоа вершины к и ,

в) к.еТ\(к I но существует ребра цвета К. , ооединяща-го шраииц к ц ^ •

Приведен полиномиальный алгоритм решения отой задачи. Б § 4 Главы 3 для некоторых результатов, полученных в работе, приведены их интерпретации в теории расписаний.

Пусть имеется п. приборов и т. требований. ( Б кочестьз приборов могут фигурировать станки, вычислительные машины, преподаватели и т.п., в качестве требований - обрабатываете детали, выполняемые программы, груши учшцихся к т.п.) Дана неотрицательная целочисленная матрица » 4 ^ С й VI,

■I ^ V :< ууъ , то Х- - - количество едкк1Щ времени, в течение . ®

которых -оо требование долаю обрабатываться 1-ым прибором.' В кавдый момент времени кавдый црибор может обрабатывать не более одного требования, и каждое требование может обрабатываться лишь одним прибором. Рассмотрим две задачи.

Задача I. Существует ли для дачного t расписание работ продолжительности "fc и соответствующее матрице Т , при котором все приборы работают непрерывно во време. I?

Задача 2. Существует ли для данного "t расписание работ продолжительности "fc и соответствующее матрице Т , при котором все приборы работают непрерывно Бремени, и все требо-вашя выполняются непрерывно во времени?

Сопоставим матрице Т двудольный мультиграфС-^СМ" Е ^ .

- - У- Т" т1 *т*

.....-'^.Л ' ав

t, • V

,. . , \ ^ YV j \ 4 V .

Легко видеть, что задачи 1 и 2 эквивалентны, соответственно, задачам существования односторонне-интервальных и кнте-овальных расквасок муяьтиграфа G- . Поэтому результаты, полу« «энные в работе для двудольных мультигрсфов, могут быть подоз-ш для теории расписаний."

В заключение выражаю глубокую благодарность моему научно-iy руководителю А.С.Асратяну за ценные советы и постоянное йш.:шие к работе. За обсуждение работы выражаю благодарность !.И.Глебсву, А.В.Косточке, JI.C.Мельникову, С.В.Севастьянову Институт математики СО All СССР), В.Н.Шевченко, В.А.Галенову ГЕО, .А.Сапожелко, В.Б.Алексееву (МГУ).

По теме диссертации опубликованы слвдувщие увботн:

1. Асратян А.О., Камадян P.P. Интервальные раскраски ре-эр мультигрэфа // Прикладная математика, ~ Ереван, 198?. •»• ж. 5„ - 0. 25-34.

2. Аератян А.О., Камаяян РД\ 0 двух .ЛГ^Р-полшйс проб-шах теории расписании /У \У кс.-/> колодкх ученых Зякавказс-

13

кдгх республик "Проблемы автоматического управления". : Тезисы докл. - Тбилиси, 1986. - С. 25 - 26.

3. Камачян P.P. Интервальные раскраски полных двудольных графов и деревьев // Препринт ВЦ АН Арм.ССР и EIY. - Ереван. -1989. - II с.

4. Каыааян P.P. О существовании и построении некоторых раскисаний с предписаниями // Известия АН Ары.ССР. Серия, технических наук. - 1989. - Т. 42. - Л G. - С. 303 - 30?.

5. Кшакян P.P. Об интервальных раскрасках полных двудольных храфов в деревьев // Проблемы теоретической кибернетики: Тез. докл. VIII Всесоюзной конф. - Горький, 1988. - Ч. I. -

С. 145 - 146.