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

АКАДЕМИЯ НАУК, СССР 4 ОРДЕНА ЛЕНИНА СШТСКОЕ ОТДЕЛЕНИЕ

; ИНСТИТУТ МШАТИКИ

Г

На правах рукописи УДК 519.I

КАЛАЛНН Рофаел Рубекошл ИТГЕГВАЛЫШЕ РЕБЕЕШЕ РАСКРАСКИ ГРАФОВ 01.01.09 - математическая кибернетика

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

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

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

Нвучный руководитель: кандидат физико-математических

наук, доден? АОРАТЯН A.C.

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

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

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

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

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

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

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

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

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

Ученый секретарь Спецвализг -»ванного совета, каццидаг физзко^иатоматичэсккх наук /А

Ю.Л.Ваоидьев

И

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

I. Актуальность темы. Исследовали» задач раскрас .с в дискретной математике уделяется большое внимание. Это обусловлено тесной связью проблемы раскраски с рядом важных прикладных задач, включая, например, составлг че оптимального расписание, минимизацию памяти программ, минимизацию числа процессоров в распределенных параллельных вычислениях и ряд других. Большая взаимссачзь существует иедпу задачами теории расписаний и задачами раскрасок, как вершинных, так и реберных.. Например, задача составления оптимального'распис.-знш экзаменационной сессии сводится к задача о хроматическом числе графа. К задаче о наховде-нии хроматического класса сводится задача составления расписаний спортивных соревнований. В связи со сказанным исследование хроматических параметров 1*ри$а имеет вачюе значонпо для теории расписали!. Изучению хроматического числа к хроматического класса посвяшени известнна работы 0.В.Бородина, Р.Л.Брукса, В.Г.Визшга, П.Катлина, А,Д.Кор>зуиова, Л.В.Косточки, Л.С.Мельникова, Н.Н.Коаана, Р. Унисона, И.Хольера, К.Э.Сетона, П.Эрдо-па.

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

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

3

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

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

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

Одним из аспектов в задачах теории расписаний является составление расписаний без прерываний. Обычно расписанием ^ез прерываний называется расписание, при котором каадое требование выполняется едншд прибором непрерывно во врэмени. Существует, : дако» ряд важнш: малоизученных задач в теории расписаний (как, наЕЭшер, составление школьных расписаний без "окон", хдо каздая учебная х-рутта и иия) каждый преподЕхахель проводя« за-

4

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

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

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

1 » ^Ф11 йиорих ребра, инцидентные вершинам мухьтнграфа,

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

Найдено необходимое условие существования гагорвальной ра-.окраски произвольного мулътигрсфа: равенство ^с-атического класса максимальной степени вервии. Как следствие получено, что для регулярного гра]эа 0* проблема определения то.го, имеет лп О- интервальную раскраску ляп нет, является «/\Г(Р~полз:ой.

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

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

5

вует интервальная т-раскраска градов этих классов.

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

'г УЛ.' (п.-* И.'

Рассмотрены такаа некстсрне задачи, соответствующие задачам о существовании и построении расписаний с предписаниями. Для некоторых из втех задач доказана их ч/ТФ-коднота, для одной' предложен полиномиальный аягориты решения.

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

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

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

?, Структура и объем работы. Диссертация изложена к т. 103 страницах меапиношеного текста. Состоит из введения, трех глав, содержащих 10 параграфов.

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

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

6

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

В Главе I дани осношие определения и обозначения. Пусть Сг - С^ССг) , VI (СУ) "" мультиграф. Степень вершины х п О- обозначил через с! (х) , максимальную из степной вориин - через Д (_(х) > хрсмати ¿кий класс С— через X (_&) . Пусть • ^¡тормлыгол па ^ \з -раскраской муль-

тиграфа 0- назовем правильную раскраску ребер 0- в цвета С, .•••>С4_. при которой з катдш цвет С. , 1 й & , окра-

л X и

гаено хотя бн одно ребро, и ребра, инцидентные каждой вершине х. £ ^ , окрааены в последовательных цветов. Непрерыв-

кой на К '^-раскраской мулътиграфа С- назовем правильную раскраску ребер С- в цвета С, С^. , при которой в каждый цвет С. , \ , окрапэно хотя бн одно ребро, и ребра, ин-

цидентные каадой варикно R , окрашени в цвета С., С(,: Пусть аХ^ - множество мультшрафов С- , для которых существует интервальная на'УСС*) "^-раскраска, к = бТ.^ • Для Сг £ ''С обозиачш чороз V/

СО)

соответственно, наименьшее и наибольшее , для которого существует интервальная на "V Ь -раскраска (сг 3 § I Гйавы I доказана Теорема 1.1.1. Если

О е К

. то

Как следствие зто15 теоремы отмечено, что для регулярного графа 0- проблема определения: 0- £ ХС или От^- СС , является иУ {Р-шхшоЛ.

В § 2 Главы Г. найдонц некоторые неравенства о параметрах гряфов класса (ГГ. . Основные результаты параграфа следующие: '

V

Теорема 1,2,1. Пусть С- - связный граф с ^ЕССэ-)^^ • ЕслнО-еЯТ, . то

Теорема 1.2.2. Для любого р > О существует 1раф О- такой. что & € а и \Л/(&:) ^ -V V .

Теорема 1,2.3. Пусть & - связный паф без греуголыш-ков. Если & е №. , ™ WC.Gr} ^ \\ГСО)\ - 1 .

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

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

Наибольший общий делитель натуральных чисел т и УХ обозначаем через <Г С***. Доказана

Теорема 1,3.1. Для любых натуральных УТЬ и УХ

пК^е ГС, •

4) если^С^^^-Ь^СК«, Д .

Следствие 1.3.1. Если ,, то тогда

и только тоэда, коэда X. — УКХ Л- ИХ— Л .

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

Пусть ¿0 дере во .V(йУ) ~ ||>Л,... }, ^ ^ 1. Через

обозначим цепь, соединяющую вершины и , через V Е1_(А ~ множество вершин и ыноже-

ство ребер этой цепи, соответственно ,1I. , \ ^ „ цепи 1.(А;. , Ъ^') ^ "ий ^ £ , вводом обозначение:

МЩ>; ) = \Е1л\ -V-,ре Е(&),

8

хгД/га Д.) ПуотьМС^=т^УЩ

Доказана

Тв'.,:ома 1.4.1. Пусть ¿0 - дерево. Тоща: 2) ы (£>)=&{£),

4) , ^ .

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

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

Задача достроения и ^ервшхькых раскрасок полных двудольных графов. Кадим условиям должны удовлетворять целые неотрицательные числа \ii\J , л,' , чтобы произвольную интервальную ш\](К ) "Ь-раскраску полного двудольного

т.,«,

графа колко было'достроить до интервальной на

\[( К , Л "Ь -раскраски полного двудольного гогфа

к , , , для какого-либо С , Т. ^ с ?

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

Теорема 2.2,5. Пусть = <Г(т. , Ь — •

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

можно разбить па полных двудольных подграфов ^ > • • • > , так что К,^. ^ окрашен интервалъно наУ^К^. ,

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

Теотю'-'я 2.2,6. Есля m/=jJLcr(m.)k'C),rt-3 <y(_rn_ trC), где J0-3 целые неотрицательные числа, то лгбута интервачьнун ка V(K "V-раскреску полного дветсяьного графа К^ „

можно достроить до интервальной на V (К / Л t --раскрлски vt i:) полного двудольного графа К „vvrn/ •

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

Б § I Глады 3 исследованы односторонне-интервальные раскраски двудольных мультиграфов.

Пусть G = CV^CG) AQG^ECG)) - двудольный мульткгрзф. Обозначил черезw^CQ-") 11 i соответственно, нат.:е-

нызее и наибольшее "t , для которого существует интервальная наV^CG) ^-раскраска Q- . Очевидно. Доказана

Теотете 3.1 Д. IlycTbG =CV¡(G\V¿C),ElG))- двудольный мулътшраф. Тоща для любого t, ^ ^ CG^) . существует интервальная HaV^G) 't.-pí101'?'101'3 мультигрефа

G.

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

Проблема.

В' х о д. Двудольный граф G = (V4CG),V^CG^, tс

С б о й с т в о. Существует непрерывная HaV-XjG) -раскраска G .

Проблема.

Вход. Двудольный граф G - (.VaCG) v V"XG) . E.CGV с

10

Д-СС-^В и целые числап.А,П.х,Угг,п.л^п.х^п.г>0 , = \ECGM.

Свойство. Существует правильная раскраска ребер О- в цвета , при которой в цвет I. окрашено Уи ро-

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

1. -'.'нокоства

X и-у верстан: х \ ,

2. Множество С цветов: С = .

3. Для каждой вершины X и Д£ны целые неотрицательные числа

кол иН(чЛЛииНОЛ.

4. Для кавдой вершины V еХ. и М даны три подмножества ТА (V*), ТдС*/), Т3 О-Л цветов, где для I -1,1

Т^еС.Т^ПТ^Ы^ при а<I<^<ъ ,

иты = с.

5. Для у?ядой пары (к , , где к <=. X. , 'У , даны три подмножества Т Ч( *»$ , ТХ((х «Т, ^">> цветов, дляи=А .

ТЧСх, ^ й с С ,Т Ч* л>))П Т*((*

-ф при

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

&=СЧСО) ,ЧСО),Есао- х « ^ ,

имеющий правильную реберную раскраску в цвета множества С . так что

I) дет каздой вершины УбЛА^т) ^(у) ¡5 с^ОЛ < НО^V»

II

2) для каллой пвщшт Vк каздого в)КбТДу) I существует ребро цвета К. , инцидентное V ,

б)К€ТьС^ I может существовать ребро цвета К , инцццент-ное V ,

в)к.еТ1и') , не существует ребра цвета К , инцидентного V ;

3) для каадой пары (х , , ада и какого

а)кеТ\с>с.*» . существует ребро цвета К. , соединяющее вершины х и ,

б) КеТ . ногат существовать ребро цвета К. соединяющее вершины кии.,

в) к.€Т*((х » не существует ребра цвета К , соединяющего вершины к ц .

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

Пусть имеется »г приборов к т. требований. ( Б качества приборов могут фигурировать станке, вттелктелншэ ияпини, преподаватели и т.п., в'качества требований - обрабатываемые детали, выполняемые программы, группы учащихся и т.п.} Дана неотрицательная целочисленная матрица Т* - (,1т.., ч 'ДI, й VI, V < т. , те "С.. - количество единиц времени, в точение

о

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

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

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

Сопоставил матрице Т двудольный мультигрсфG- -(\[ ^С.^) ,

ребро (х,,^

имеет кратность "t^, i 5 $ vi 4 ^ ^ m..

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

т

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

В заключение вырекаю глубокую благодарность моему научному руководителю А.С.Асратяну за ценные советы и постоянное внимание к работе. За обсузденпо работы ыгражаю благодарность 1,И.Глебсву, А.В.Косточке, Л.О,Мельникову, С.В.Севастьянову [Институт математики СО АН СССР), В.Н.Шевченко, В. А.Таланову ,ПУ), .А.Сапожедко, В.Б.Алексееву Ш1У).

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

1. Асратлн А.С., Кшалян P.P. Интервальные раскраски ре-ар мультиграфа // Прикладная математика, - Ереван, 1987. -ып. 5., - С, 25-34.

2. Асратян А.У,, Камалнн Р„Р. О двух .ЛГФ-гкшшх проб-эмах теории расписаний // \\f кс.-/1 молодых ученых Зякавкаэс-

13

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

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

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

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

С. 145 - 146.