Задачи раскраски инцидентеоров и их приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Институт математики им. С. Л. Соболева

На правах рукописи УДК 519.174.7

Пяткин Артем Валерьевич

ЗАДАЧИ РАСКРАСКИ ИНЦИДЕНТОРОВ И ИХ ПРИЛОЖЕНИЯ

01.01.09 — математическая кибернетика

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

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

А. И. Ерзин

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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ........................................................ 4

ГЛАВА 1. Исходная задача........................................ 13

1. Задача раскраски инциденторов........................ 13

2. Примеры задач раскраски инциденторов................ 15

3. Содержательная постановка исходной задачи........... 20

4. Математическая модель исходной задачи............... 23

5. Первый алгоритм решения исходной задачи

(алгоритм А\).......................................... 27

6. Второй алгоритм решения исходной задачи

(алгоритм Аг)..........::;г.;.................... 30

7. Приближенный алгоритм меньшей трудоемкости....... 32

ГЛАВА 2. Варианты исходной задачи............................. 34

8. Случай произвольных пропускных способностей........ 34

9. Задача с двумя сеансами................................ 35

10. Случай ограниченной памяти.......................... 44

11. Доказательство гипотезы Визинга-Мельникова

в двух частных случаях............................... 46

11.1. Случай малой степени ориентированной части мультиграфа.......................................48

11.2. Случай малой степени мультиграфа.............. 52

12. Обобщение исходной задачи............................57

13. Задача равномерного распределения информации между т центральными ЭВМ......................... 66

13.1. Постановка задачи................................66

13.2. О приближенных алгоритмах решения

задачи о камнях................................... 68

ЗАКЛЮЧЕНИЕ ................................................... 71

ЛИТЕРАТУРА .................................................... 72

з

Введение

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

Среди задач теории графов особо можно выделить задачи раскраски (окраски) графов. Под раскраской понимается отображение множества объектов раскраски во множество целых положительных чисел [цветов). Объектами раскраски, как правило, являются вершины графа, его ребра или объединение множеств вершин и ребер. Соответствующие раскраски называются вершинными, реберными и тотальными. В зависимости от налагаемых ограничений различают правильные [7,10], предписанные [14,22,29], дистрибутивные [4] и многие другие раскраски. Наиболее известны и хорошо изучены правильные раскраски, в которых нужно использовать наименьшее число цветов, так чтобы при этом никакие два смежных или инцидентных объекта не были окрашены одинаковыми цветами Это наименьшее число цветов называется в зависимости от объектов раскраски вершинным, реберным или тотальным хроматическим числом графа. Заметим, что

правильная тотальная раскраска графа должна включать в себя как правильную реберную, так и правильную вершинную его раскраски.

Теоретическую оценку алгоритмической сложности различных классов задач дает теория NP-пoлныx проблем, основанная Куком [11] и Карпом [9]. В этой теории рассматривается класс КР задач распознавания свойств, разрешимых за полиномиальное время недетерминированной машиной Тьюринга, и класс Р задач распознавания свойств, разрешимых за полиномиальное время детерминированной машиной Тьюринга.

В классе № выделяются так называемые ИР-полные задачи, к которым полиномиально сводится любая задача из КР. Под полиномиальной сводимостью задачи А распознавания свойств к задаче В понимается существование полиномиального алгоритма построения по исходным данным любой индивидуальной задачи /д данных некоторой индивидуальной задачи 1в, причем каждая индивидуальная задача /д имеет ответ "да"тогда и только тогда, когда соответствующая ей индивидуальная задача 1в имеет ответ "да". Следовательно, полиномиальный алгоритм решения КР-полной задачи может существовать тогда и только тогда, когда Р=№. Обширный список ЫР-полных задач приведен в книге Гэри и Джонсона [5].

Оптимизационную задачу называют ЫР-труднощ если к ней полиномиально сводится некоторая КР-полная задача. Основной вывод из этой сводимости заключается в том, что существование полиномиаль-

ного алгоритма хотя бы для одной NP-трудной задачи влечет существование такого алгоритма для всех задач из NP, и, следовательно, P=NP.

Многие из оптимизационных раскрасочных задач, в том числе задачи вершинной и реберной раскраски графов, являются NP-трудными [5],[24]. Можно выделить два подхода к решению таких задач.

Первый подход заключается в построении приближенных алгоритмов. Обозначим через Fa(I) значение целевой функции индивидуальной задачи I, найденное некоторым алгоритмом А, а через F*(I) — оптимальное значение целевой функции. Алгоритм А имеет абсолютную погрешность к, если

sup I F*(I) - Fa(I) |= i

и относительную погрешность £, если

supl (F'(I)-FA(I))/F'(I) \=е.

I

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

Второй подход к решению NP-трудных задач заключается в выделении более простых, чем общая задача, подзадач. Прежде всего речь идет о полиномиально разрешимых подзадачах. Например, NP-трудная задача реберной раскраски графов (Хойлер [24]) допускает полиномиальное решение на классе двудольных графов [8,30]. Но иногда выделение подзадачи оказывается полезным даже в том случае,

если сама выделяемая подзадача продолжает оставаться КР-трудной. Так, упомянутая выше задача реберной раскраски графов получается ограничением задачи вершинной раскраски графов на класс реберных графов (т.е. является подзадачей последней). Но в то время как для раскраски вершин графа не существует алгоритма с заданной абсолютной погрешностью (если Р^ [5], то для реберной раскраски такой алгоритм существует [1-3]. Это алгоритм Визинга, строящий решение, не более чем на единицу отличающееся от оптимального (для мультиграфов абсолютная погрешность не превосходит мощности максимального мультиребра).

Для некоторых КР-трудных задач с числовыми параметрами также можно предложить точный алгоритм, время работы которого ограничено полиномом не только от размерности задачи, но и от значений числовых параметров. Такой алгоритм называется псевдополиноми-алъным. Например, псевдополиномиальным алгоритмом является метод динамического программирования для решения таких задач, как РЮКЗАК, РАЗБИЕНИЕ и некоторых других [5,16].

Описанная выше терминология будет использоваться в дальнейшем на протяжении всей диссертации.

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

книге Йенсена и Тофта [26], которая посвящена описанию раскрасоч-ных задач и их приложений.

В диссертации исследуются задачи раскраски объектов, ранее в теории графов практически не расматривавшихся. Это инциденторы, или "половинки дуг". Формально инцидентор определяется в ориентированном графе как упорядоченная пара, состоящая из вершины и инцидентной ей дуги. Первоначально этот термин был введенн Зыковым [7] для обозначения элементов множества V х Е. В последствии он был предложен Визингом и Мельниковым [35] вместо применяемого ранее автором диссертации [42] термина "полудуги".

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

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

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

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

Примерами рассматривавшихся в диссертации сетей могут являться широкополосные цифровые сети, активно разрабатываемые в США, Японии, Канаде и ряде стран Западной Европы начиная с середины 80-х годов. Для них характерна иерархичиеская организация с высокой пропускной способностью каналов связи верхнего уровня и звездной структурой подключения абонентских терминалов нижнего уров-

ня. Создание таких сетей стало возможным благодаря появлению быстродействующих микропроцессоров и дешевого волоконно-оптического кабеля. Более подробно с широкополосными сетями можно ознакомиться в работах Лазарева [12], Захарова [6] и других авторов [21,23].

Диссертация состоит из введения, двух глав, заключения и списка литературы.

В главе 1 формулируются основные изучаемые в диссертации задачи. Во-первых, это формулировка задачи окраски инциденторов ориентированного мультиграфа (раздел 1) и примеры, демонстрирующие уже решенные задачи окраски инциденторов (раздел 2). Во-вторых, это исходная задача оптимизации расписания передачи сообщений в локальной сети связи, различные вариации которой рассматривается во всей остальной диссертации. Содержательная постановка исходной задачи приведена в разделе 3, построение математической модели — задачи окраски инциденторов — производится в разделе 4. Наконец, завершают главу 1 два алгоритма решения основной задачи (в ее теоретико-графической постановке) в разделах 5 и 6, а также некоторые соображения по снижению трудоемкости этих алгоритмов в разделе 7.

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

отметим лишь, что в этой главе особенно ярко проявилась удивительная гибкость математической модели. Такие разные вариации, как ограничения на память (раздел 10), ограничения на способы передачи информации (разделы 9 и 11), наконец, ограничения на саму структуру сети связи (раздел 12) — все они укладывались в рамки задачи окраски инциденторов! И лишь в последнем, завершающем главу 2 разделе 13 сформулирована задача, для которой этих рамок оказалось недостаточно. Оказалось, что для того чтобы свести задачу равномерного распределения информации между т центральными ЭВМ к исходной задаче, необходимо предварительно решить задачу о камнях, для которой приводится анализ аппроксимационных схем и алгоритмов ее решения.

Основные результаты диссертации сформулированы в заключении. Завершает диссертацию список использованной литературы, включающий 46 работ.

Основные результаты диссертации докладывались на семинарах Института математики СО РАН по исследованию операций, теории графов, дискретным экстремальным задачам, избранным задачам комбинаторики, семинаре Института вычислительной математики и математической геофизики по моделированию и оптимизации коммутационных сетей, а также на конференции ШРШМ-96 (Новосибирск, 1996), Первой научной молодежной школе по дискретной математике и ее приложениям (Москва, 1997) и Второй научной молодежной шко-

ле по дискретной математике и ее приложениям (Нижний Новгород, 1998). По материалам диссертации опубликовано 5 работ.

Автор выражает искреннюю благодарность своему научному руководителю Ерзину А.И., а также Бородину О.В., Дементьеву В.Т., Косточке A.B., Мельникову JI.C. и Шамардину Ю.В. за всестороннюю помощь и поддержку в работе.

Глава 1. Исходная задача

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

1 Задача раскраски инциденторов

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

Пусть С = (V, Е) — ориентированный мультиграф без петель, с множеством вершин V и множеством дуг Е.

Определение 1. Инцидентором или полудугой будем называть упорядоченную пару (у,е), где ь Е V, е £ Е и вершина V инцидентна

дуге е.

Для дуги е = (и, у), инцидентор (и,е) будем называть начальным, а инцидентор (г>,е) конечным. Множество всех инциденторов муль-тиграфа <2 обозначим через I.

Определение 2. Раскраской инциденторов называется произвольное отображение / : / —> где — это множество целых положительных чисел.

Кроме того считаем, что для каждой дуги е Е Е задан двухместный предикат ре(а,Ь), определенный для любых а,6 £ Z+. Все рассматриваемые в диссертации предикаты, как правило, можно будет выразить в виде некоторого линейного соотношения для чисел а и Ь.

Определение 3. Раскраска инциденторов / называется правильной, если для любых двух инциденторов (г;, ех), (г>, е^) € I (имеющих общую вершину у) выполнено условие /(г?,ех) ф /(-г;, е2).

Определение 4. Раскраска инциденторов / называется допустимой, если для каждой дуги е = (ад, у) инциденторы которой окрашены в цвета /(и, е) = а, /(г/, е) = 6, выполняется предикат ре(а, 6).

Задача раскраски инциденторов заключается в том, чтобы найти минимальное число Т, для которого существует правильная и допустимая раскраска инциденторов мультиграфа (7 цветами {1,..., Т}.

Обозначим через во максимальную степень мультиграфа О (в дальнейшем, если это не будет приводить к путанице, индекс будем опускать). Из свойства правильности раскраски инциденторов сразу сле-

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

Таким образом, для более глубоких исследований задачи желательно задание предикатов ре(а,Ь) для каждой дуги е Е Е в явном виде. Каждое такое задание определяет некоторый частный случай задачи окраски инциденторов. Поэтому в дальнейшем для описания частных случаев задачи окраски инциденторов будем ограничиваться лишь указанием в явном виде предиката ре(а,Ь) для каждой дуги ееЕ.

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

2 Примеры задач раскраски инциденторов

Пример 1. Пусть для каждой дуги е £ Е задан предикат ре(а, Ъ) = {а = Ь}. В этом случае каждая дуга красится в один цвет, и любые две дуги, имеющие общую вершину, должны быть раскрашены разными цветами ввиду условия правильности раскраски. Таким образом, имеет место классическая задача реберной раскраски мультиграфа

(искомое Т есть хроматический индекс мультиграфа С). Хойлер [24] доказал, что эта задача NP-тpyднa. Известны лишь приближенные алгоритмы ее решения, в частности, уже упомянутый во введении алгоритм Визинга [1-3]. На рисунке 1 слева изображена раскраска дуг, а справа — раскраска инциденторов некоторого мультиграфа.

Рис. 1

Пример 2. Пусть для каждой дуги е £ Е задан предикатре(а, Ь) — {а ф 6}. В этом случае задача окраски инциденторов сводится к задаче реберной раскр�