Раскраска инциденторов и другие задачи на графах: алгоритмический аспект тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Пяткин, Артем Валерьевич

Оглавление диссертации доктор физико-математических наук Пяткин, Артем Валерьевич

Глава 1. Раскраска инциденторов: происхождение и приложения

1.1. Раскраска инциденторов: происхождение и приложения

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

1.3. Математическая модель исходной задачи и алгоритмы сё решения.

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

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

1.6. Задача с двумя сеансами передачи сообщений.

1.7. Задача с ограниченной памятью.

1.8. Доказательство гипотезы Визинга-Мельникова в двух частных случаях.

1.9. Передача сообщений в двухуровневой сети.

1.9.1. Случай большой пропускной способности каналов связи верхнего уровня.

1.9.2. Случай двух центральных ЭВМ, соединённых шиной пропускной способности 1.

Глава 2. Раскраска инциденторов: исследование модели

2.1. Задача взвешенной раскраски инциденторов.

2.1.1. Доказательство МР-полноты.

2.1.2. Свойства минимальной раскраски.

2.1.3. Паросочетание наименьшей мощности, покрывающее заданные вершины мультиграфа.

2.1.4. Верхние оценки для инциденторного хроматического числа.

2.2. (к, I)-раскраска инциденторов.•.

2.2.1. (0,1)-раскраска инциденторов.

2.2.2. (1,1)-раскраска инциденторов.

2.2.3. Общий случай (к, ¿)-раскраски инциденторов.

2.3. Предписанная раскраска инциденторов.

2.4. Раскраска инциденторов взвешенного неориентированного мультиграфа.

Глава 3. Вершинная и рёберная раскраски графов

3.1. Интервальная раскраска (3,4)-бирегулярного графа

3.2. Графы Эрдёша и Дирака.

3.2.1. Первый пример 6-регулярного 4-критического графа

3.2.2. Метод поиска графов Эрдёша и Дирака

3.2.3. Циркулянты Эрдёша pi Дирака чётной степени г,

3.3. Покрывающая вырожденность и хроматическое число

Глава 4. Нумерации графов

4.1. Предписанная радио-нумерация.

4.2. Суммируемые и целочисленно суммируемые графы.

4.2.1. Число суммируемости полного двудольного графа

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

4.2.3. Однородные целочисленно суммируемые графы

4.3. Графы, представимые в виде слов.

Глава 5. Точные экспоненциальные алгоритмы на графах

5.1. Доминирущие множества и доматическое число.

5.1.1. Алгоритм, перечисляющий все минимальные доминирующие множества.

5.1.2. Алгоритм для поиска доматического числа.

5.2. Множества, разрезающие циклы.

5.2.1. Алгоритм для поиска максимального по мощности индуцированного леса.

5.2.2. Оценка для числа максимальных по включению индуцированных лесов.

Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Введение диссертации (часть автореферата) на тему «Раскраска инциденторов и другие задачи на графах: алгоритмический аспект»

Характерной особенностью дискретной математики является то, что в этой области многие доказательства являются конструктивными, позволяющими непосредственно построить искомый объект или выделить его часть, обладающую некоторыми интересными с точки зрения исследователя свойствами. Возможно это связано с тем, что большинство задач дискретной математики возникло из приложений, где требуется не только доказать возможность достижения цели, но и предъявить алгоритм, позволяющий это сделать. Так называемые «теоремы существования», которые только доказывают, что объект существует, но не дают при этом никаких идей, как его можно построить, встречаются в дискретной математике довольно редко. И даже если такие теоремы появляются, то исследователи, как правило, продолжают работать над поиском конструктивных доказательств. Классическим примером вышесказанного может служить знаменитая теорема Эрдёша 1959 года о существовании графа с произвольными наперёд заданными охватом и хроматическим числом. Доказательство П. Эрдёша [38] было вероятностным; оно не позволяло непосредственно построить такой граф. Поэтому позднее было найдено несколько конструктивных доказательств этой теоремы. Их предложили Л. Ловас ([69], 1968), Й. Нешетрил и В. Рёдль ([78], 1979) и А. Любоцкий, Р. Филипс и П. Сарнак ([72], 1988). Другим примером является доказанная Л. Ловасом ([70], 1978) гипотеза М. Кнезера ([60], 1955) о хроматическом числе графов Кнезера. Доказательство Ловаса (равно как и более простые доказательства, полученные позднее И. Барани ([28], 1978),

К. С. Саркария ([85], 1990) и В. Л. Дольниковым ([18], 1993)) опиралось на некоторые топологические результаты и было неконструктивным, т. е. из него нельзя было получить алгоритм построения раскраски графов Кнезера в требуемое число цветов. И лишь в 2004 году И. Матушеку [75] удалось найти комбинаторное доказательство гипотезы Кнезера.

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

Теория алгоритмической сложности возникла в 70-х годах прошлого века, когда впервые появилось понятие NP-тpyдныx задач, т. е. таких задач, для которых скорее всего (если Р не равно КР; далее в диссертации будем всюду придерживаться этой гипотезы) не существует алгоритма решения, время работы которого ограничено полиномом от длины входных данных задачи. В связи с этим первоочередным вопросом при анализе дискретной экстремальной задачи является определение её сложностного статуса. Либо она принадлежит классу Р полиномиально разрешимых задач, либо к классу КР-трудных задач. В последнем случае приходится либо использовать быстрые приближённые, либо точные экспоненциальные алгоритмы решения. При этом хотелось бы иметь некоторую оценку качества работы таких алгоритмов. В первом случае это оценка точности получаемого решения, а во втором — оценка времени работы (пусть экспоненциальная, но существенно лучшая чем при полном переборе всех допустимых решений).

Отметим, что для доказательства полиномиальной разрешимости задачи распознавания как правило требуется найти хорошую характеризацию (легко проверяемое условие) для примеров как с положительным, так и с отрицательным ответами. С другой стороны, для доказательства КР-полноты некоторой задачи зачастую приходится строить примеры объектов, обладающих теми или иными свойствами. Впоследствии эти объекты используются как «кирпичики» при построении сведения известной NP-пoлнoй задачи к исследуемой. Таким образом, в обоих случаях определение сложностного статуса задачи базируется на изучении структурных свойств исследуемых объектов или построении примеров с определёнными свойствами.

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

Основным предметом изучения в диссертации являются различные задачи раскраски мультиграфов и прежде всего — раскраска инцидеп-торов. Под ипцидентором в ориентированном мультиграфе понимается упорядоченная пара, состоящая из вершины и инцидентной ей дуги. Его удобно трактовать как половину дуги, примыкающую к данной вершине. В задаче раскраски инциденторов требуется найти минимальное число цветов, в которое можно раскрасить все инцидеиторы мультиграфа с соблюдением заданных условий на цвета смежных (примыкающих к одной и той же вершине) и сопряжённых (имеющих общую дугу) инциденторов. Это новый, введённый автором [104], класс задач, включающий в себя, в частности, классические задачи вершинной и рёберной раскраски. Модель инциденторной раскраски оказывается удобной при исследовании задачи передачи сообщений в локальной сети связи. С её помощью можно выразить различные ограничения на параметры каналов связи, способы передачи сообщений и структуру сети. При этом варьируются лишь ограничения на цвета сопряжённых инциденторов и структуру мультиграфа, сама же задача остаётся в рамках инциденторной раскраски.

Задачи раскраски инциденторов находят себе применение и в теории расписаний. Так классическая задача JOB SHOP с единичными длительностями операций и с двумя операциями каждой работы эквивалентна задаче (1, оо)-раскраски инциденторов. А более общая задача (к,1)

раскраски инцденторов эквивалентна вышеописанному варианту задачи JOB SHOP с дополнительными условиями на длительность интервала между двумя операциями каждой работы. Результаты по раскраске инциденторов тем самым помогают решить некоторые варианты задачи JOB SHOP (см. [27]).

Однако задача раскраски, инциденторов представляет интерес и сама по себе. Различными исследователями рассматривались вопросы её алгоритмической сложности [100, 101], обобщения на случай неориентированных и частично ориентированных графов [6, 9, 10, 13, 14, 101] и гиперграфов [12], интервальная [4, 6], тотальная [3, 14] и предписанная [2, 110] инциденторная раскраски и многие другие. Задачи раскраски инциденторов являются новым направлением в теории графов.

Заметим, что инциденторы встречались в работах по теории графов и ранее, но только как вспомогательный инструмент, а не как основной объект для изучения. Например, в работе [31] показано, что один из частных случаев задачи о сильной рёберной раскраске мультиграфа сводится к задаче раскраске инциденторов неориентированного графа, в которой (в терминах настоящей диссертации) смежные, сопряжённые и смежные к сопряжённым инциденторы должны получать разные цвета. Этой задаче был впоследствиР1 посвящёно несколько работ [46, 37, 66, 90]. Отметим, однако, что такая инциденторная раскраска является слишком специфической и из неё нельзя получить класс задач инциденторной раскраски, исследуемых в диссертации.

Диссертация состоит из введения, пяти глав и списка литературы, состоящего из 145 наименований.