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

На правах рукописи

ПЯТКИН Артем Валерьевич

РАСКРАСКА ИНЦИДЕНТОРОВ И ДРУГИЕ ЗАДАЧИ НА ГРАФАХ: АЛГОРИТМИЧЕСКИЙ

АСПЕКТ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

003473842

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

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

003473842

Работа выполнена в Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН

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

A. Д. Коршунов

доктор физико-математических наук

B. Н. Касьянов

доктор физико-математических наук М. Ю. Хачай

Ведущая организация: Учреждение Российской академии

наук Институт вычислительной математики и математической геофизики Сибирского отделения РАН

Защита состоится 9 сентября 2009 г. в 16 час. 00 мин. на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН по адресу: 630090 г. Новосибирск, пр. Академика Коптюга 4, к. 417.

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

Автореферат разослан

» 4

и/аир

2009 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

Ю. В. Шамардин

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

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

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

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

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

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

Однако задача раскраски инциденторов представляет интерес и сама по себе. Различными исследователями рассматривались вопросы её алгоритмической сложности [22, 23], обобщения на случай неориентированных и частично ориентированных графов [5, 6, 7, 9, 10, 23] и гиперграфов [8], интервальная [4, 5], тотальная [3, 10] и предписанная [2, 32] инциденторная раскраски и многие другие. Задачи раскраски инциденторов составляют новое направление в теории графов.

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

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

ветвления и варьирования меры (так называемый метод «измеряй и властвуй»). Из оригинальных методов следует отметить разработанный в главе 3 метод поиска графов Эрдёша и Дирака, позволяющий свести сложную задачу определения 4-критичности нормальных циркулянтов к проверке выполнения нескольких арифметических соотношений для их параметров.

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

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

Основными результатами диссертации являются:

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

2. Доказательство ИР-полноты задачи раскраски инциденторов взвешенного ориентированного и неориентированного мультигра-фа.

3. Определение точной формулы для инциденторного (к, сю)-хроматического числа и нахождение верхних и нижних оценок для инциденторного (/с, ^-хроматического числа.

4. Построение вершинно-транзитивных г-однородных г-связных 4-критических графов для г 6 {6,8,10,12,14,16}, что частично подтверждает гипотезы Эрдёша (1989) и Дирака (1960).

5. Построение первого примера графа, покрывающая вырожденность которого не равна хроматическому числу.

6. Доказательство неулучшаемых верхних оценок на минимальную ширину спектра в зависимости от обхвата графа в задаче о предписанной радио-нумерации.

7. Построение примеров непредставимых графов и характери-зация графов, представимых в виде слов, через ориентации графа.

8. Доказательство верхних оценок для максимального числа минимальных по включению доминирующх множеств и множеств, разрезающих циклы, в n-вершинном графе.

Апробация работы. Результаты диссертации докладывались автором на следующих российских и международных конференциях: Второй сибирский конгресс по прикладной и индустриальной математике (INPRIM-96; Новосибирск, 1996); IX межгосударственная школа-семинар «Синтез и сложность управляющих систем» (Нижний Новгород, 1998); 6th Twente workshop on graphs and combinatorial optimization (Enschede, Netherlands, 1999); Международная конференция «Дискретный анализ и исследование операций» (DAOR-2000; Новосибирск, 2000); Конференция молодых ученых, посвященная 100-летию М. А. Лаврентьева (Новосибирск, 2000); Конференция молодых ученых по математике, математическому моделированию и информатике (Новосибирск, 2001); Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002; Новосибирск, 2002); International conference «Graph theory 2002» (Odense, Denmark, 2002); III конференция молодых учёных, посвящённая М. А. Лаврентьеву (Новосибирск, 2003); Российская конференция «Дискретный анализ и исследование операций» (DAOR-2004; Новосибирск, 2004); 8th Nordic combinatorial conference (Aalborg, Denmark, 2004); International colloquium on graph theory (ICGT'05; Hyeres, France, 2005); 16th International symposium on algorithms and computation (ISAAC 2005; Sanya, China, 2005); Winter school in algorithms, graph theory and combinatorics (Finse, Norway, 2006); 3rd Conference on optimal discrete structures and algorithms (ODSA 2006; Rostock, Germany, 2006); Российская конференция «Математика в современном мире», посвященная 50-летию Института математики им. С. Л. Соболева СО РАН (Новосибирск, 2007). Диссертация прошла апробацию на следующих семинарах Института математики им. С. Л. Соболева СО РАН: «Теория графов» (руководитель Л. С. Мельников), «Дискретные экстремальные задачи» (руководитель Э. X. Гимади), «Дискретный анализ» (руководители А. А. Евдокимов и А. Д. Коршунов). Кроме того, результаты по раскраске инциденторов (главы 1 и 2) докладыва-

лись на заседании Президиума СО РАН 3 сентября 2003 года.

Публикации и личный вклад. По теме диссертации автором опубликовано 47 работ, 27 из которых являются статьями в центральных и зарубежных журналах. В совместных работах вклад соискателя является основным; ему принадлежат ключевые идеи доказательств. Конфликт интересов с соавторами отсутствует.

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

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

Во введении даётся общая характеристика работы, а также приводятся основные результаты диссертации.

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

Инцидентором в ориентированном графе й — (V, Е) без петель называется упорядоченная пара (у,е), где у € V, е € Е и вершина у инцидентна дуге е. Инцидентор (г;, е) удобно трактовать как половину дуги е, примыкающую к вершине у. Два ин-цидентора (у, е\). (у,е2), примыкающие к одной и той лее вершине у, называются смежными. Для дуги е — иу инцидентор (и, е) называется начальным, а инцидентор (у, е) — конечным. Начальный и конечный инциденторы одной дуги называются сопряжёнными. Множество всех инциденторов мультиграфа С? обозначается через I. Раскраской инциденторов называется произвольное отображение / : I —> Z+, где — это множество целых положительных чисел, называемых также цветами.

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

Раскраска инциденторов / называется правильной, если смежные инциденторы раскрашены разными цветами. В диссертации рассматривается, в основном, правильная раскраска инциденторов. Пусть для каждой дуги е Е Е задан двухместный предикат ре(а, 6), определенный для любых а, Ь £ Тогда раскраска инциденторов / называется допустимой, если для каждой дуги е = (и, у), инциденторы которой окрашены в цвета /(гг, е) = а и /(у, с) = Ь, истинен предикат ре(а,Ь). Задача раскраски инциденторов заключается в том, чтобы найти минимальное число называаемое инциденторным хроматическим числом, для которого существует правильная и допустимая раскраска инциденторов мультиграфа С? цветами из интервала [1,Х/]-

Исходная задача передачи сообщений в локальной сети связи заключается следующем. Задана локальная коммуникационная сеть, состоящая из центральной ЭВМ и п шин пропускной способности 1, соединяющих её с периферийными объектами. Для каждой пары объектов заранее известен общий объём информации <1ц, который г-й объект должен передать ]-му. Считается, что <1ц = О для любого г. Передача сообщений может быть организована следующими способами:

1) Центральная ЭВМ соединяет г-ю шину с напрямую. В этом случае единица информации из г-го объекта передается в ^'-й (или, наоборот, из ^'-го в г-й) без запоминания в центральной ЭВМ за одну единицу времени.

2) Информацию, которую г-й объект должен передать .7-му, можно сначала получить по г-й шине и запомнить в центральной ЭВМ, а затем передать по ¿-й шине адресату. Считатеся, что при

этом память центральной ЭВМ больше суммы всех (113.

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

Пусть С = (V, Е) — п-вершинный ориентированный мульти-граф с множеством вершин V и множеством дуг Е, в котором г-й шине соответствует г-я вершина графа, а число рёбер, ведущих из г-й вершины в ^'-ю, равно 1,} = 1,2,..., п. Таким образом, каждая дуга мультиграфа соответствует одной единице информации, которую требуется передать из г-го объекта в ]-1\. Для построения расписания передачи сообщений для каждой единицы информации необходимо задать два момента времени: когда она передаётся по первой шине и когда — по второй. При первом способе передачи информации оба этих момента совпадают; при втором способе передача информации по первой шине должна предшествовать второй. Эти моменты времени можно трактовать как цвета инциденторов дуги, соответствующей данной единице информации. Поскольку пропускные способности всех шин равны 1, цвета любых смежных инциденторов должны быть различны. В итоге получаем задачу поиска правильной раскраски инциденторов мультиграфа С с предикатом ре(а, Ь) = {а < Ь} для каждой дуги е £ Е.

Доказана следующая

Теорема 1. В любом ориентированном мулътиграфе б степени А с предикатом ре(а,Ь) — {а < 6} для каждой дуги е € Е существует правильная допустимая раскраска его инциденторов в А цветов. Более того, такая раскраска может быть построена за время <Э(п2А2).

Для этой задачи предложен также щшближённый алгоритм сложности 0(п2А) с погрешностью 2п/уА.

Рассмотрены следующие модификации исходной задачи.

1. В случае произвольных пропускных способностей шин рассматривается задача с предикатом ре(а,Ь) = {а < Ь) для каждой дуги е£ £ и доказывается, что XI < А + 1.

2. В задаче с двумя сеансами передачи сообщений помимо информации дц, г,] = 1,2,..., п, присутствует также информация ¿[р г, = 1, 2,..., п, которая станет доступной для передачи лишь в некоторый момент t > 0. Эта задача сводится к раскраске инциденторов мультиграфа С = (V, Е\ и Ео) с предикатами ре(а,Ь) =

{а < Ь} для каждой дуги е € Е\ и ре(а, Ь) = {£ < а < Ь} для каждой дуги е € Е2. Для любого к = {1,2,..., ¿} найдены необходимое и достаточное условия того, что XI < Д + к (теорема 2).

3. В задаче с ограниченной памятью <5 возникают трудности с использованием второго способа передачи сообщений (в частности, если б? = 0, то второй способ вообще запрещён, и получается задача рёберной раскраски мультиграфа). Однако, если (5 сравнительно велико, то задача с ограниченной памятью сводится к задаче раскраски инциденторов с предикатом ре(а,Ь) = {Ь — 1 < а < Ь] для каждой дуги е. Доказаны две теоремы:

Теорема 3. Если (5 > то существует допустимое рас-

писание передачи сообщений длины Д при чётном Д и длины Д + 1 при нечётном Д.

Теорема 4. Если <5 > п, то существует допустимое расписание передачи сообщений длины Д.

4. Гипотеза Визита-Мельникова. Пусть в исходной задаче заранее указано, какие сообщения должны передаваться первым способом, а какие — вторым. Такая задача сводится к следующей задаче раскраски инциденторов.

Пусть (7 = {V; Ь и А) — смешанный мультиграф с множеством дуг (ориентированных рёбер) А и множеством звеньев (неориентированных рёбер) Ь. Для каждой дуги е € А задан предикат ре(а, Ь) = {а < Ь}, а для каждого звена I Е Ь — предикат р/(а, Ь) = {а = Ь}. Эта задача впервые была рассмотрена В. Г. Визингом и Л. С. Мельниковым [20]. Там же была высказана гипотеза, что что можно построить раскраску инциденторов мультиграфа С? в тах{Д + 1,х'} цветов, где х' — эт0 рёберное хроматическое число мультиграфа й. Гипотеза Визинга Мельникова доказана в двух следующих частных случаях.

Теорема 5. Пусть к = х' ~ Д- Тогда если степень мультиграфа О а = (У, ^4) не превосходит к, то инциденторы мультиграфа С можно раскрасить в х! цветов.

Теорема 6. Для любого смешанного мультиграфа (7 = (У, Ь и А) степени не больше 3 существует раскраска его инциденторов цветами 1,2,3,4.

5. Рассмотрим двухуровневую сеть, на нижнем уровне которой расположены объекты, соединённые со своими центральными ЭВМ шинами пропускной способности 1 (как в исходной задаче), а на верхнем — произвольная сеть из центральных ЭВМ, соединённых между собой каналами связи с заданной пропускной способностью. Если пропускные способности каналов связи верхнего уровня достаточно велики (не меньше общего числа объектов нижнего уровня), то задача передачи сообщений сводится к задаче раскраски инциденторов взвешенного мультиграфа С? = (V, Е): каждая дуга е £ Е имеет вес ъи(е) 6 {1,2,...,(!}, где ё. — диаметр сети верхнего уровня; для каждой дуги е € Е задан предикат ре(а,Ь) = {а < Ь — ш(е)}. Эта задача подробно изучается в главе 2; здесь же рассмотрен случай одинаковых весов и доказана

Теорема 7. Пусть на каждой дуге мультиграфа С = (V, Е) задан предикат ре(а,Ь) = {а < Ь—(1). Тогда XI = тах{Д, с1+&+, (1+ А"}.

Если же пропускная способность каналов связи верхнего уровня мала, то далее в случае двух центральных ЭВМ, соединённых шиной пропускной способности 1, приходится расширять модель инциденторной раскраски, вводя «средние части» дуг. Рассматривается обобщённая задача инциденторной раскраски ориентированного мультиграфа С = (V; Е), где V = У\ и ¥2, У\ П = 0, Е — Ео и Е\ и Е2, дуги из Ег соединяют вершины из Ц (г = 1, 2), а дуги из Ео соединяют вершины из У\ с вершинами из У%. Дуги из Ео соответствуют тем сообщениям, для передачи которых используется шина верхнего уровня. Пусть |£о| = а степень мультиграфа С равна А. Если дуга е принадлежит Е\ или Е2, то красятся только её инциденторы; при этом требуется выполнение предиката ре(а,Ь) — (а < Ь). Если дуга е € Ео, то помимо инциденторов красятся также её «средняя часть». В этом случае необходимо выполнение предиката де(а,с,Ь) = (а < с < Ь), где а — цвет начального инцидентора, Ь — цвет конечного инцидентора, а с — цвет «средней части» дуги е. Так как цвет «средней части» дуги из Ео соответствует моменту времени, в который данная единица информации передается по шине верхнего уровня, то естественным образом получается следующее дополнительное ограничение: все цвета средних частей дуг из Ео должны быть различны. Нижняя

оценка ^ тах{/с, А} сразу вытекает из ограничений. Однако

она не является точной при к < А; в этом случае построен класс мультиграфов С таких, что х7(С?) > А + 1. При к > А оценка точна, что вытекает из следующей теоремы.

Теорема 8. Для любого мулътиграфа <3 степени А с \Ео\ = к справедлива оценка х/(б?) < тах{&, А + 1}.

Последний результат получен совместно с Н. С. Плехановой.

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

1. Задача инциденторной раскраски взвешенного мулътиграфа. Результаты получены в соавторстве с В. Г. Визингом. Исследованы случаи как ориентированного, так и неориентированного мультиграфа. Пусть каждой дуге (ребру) мультиграфа без петель сопоставлено некоторое целое неотрицательное число ги{е), называемое весом дуги (ребра). В ориентированном случае для каждой дуги е Е Е задан предикат ре(а,Ь) = {Ь — а > г«(е)}. В неориентированном случае для каждого ребра е Е Е задан предикат ре(а,Ь) = {|Ь — а\ > и>(е)}. Доказана КР-полнота соответствующих задач распознавания как в ориентированном (теорема 9), так и в неориентированном случаях (теорема 19). Также получены верхние и нижние оценки для инциденторного хроматического числа взвешенного мультиграфа.

В случае ориентированного мультиграфа для каждой дуги е рассматривается величина Н(е) = тах{с/+(м), ¿"(и)} + ги(е). Полагается ?/(С) = тах{/г(е) | е Е Е}. Доказаны две теоремы.

Теорема 10. Для любого мулътиграфа С? имеет место неравенство < тах{Д((7), ?7((7)}.

Теорема 11. Существует алгоритм, находящий раскраску инциденторов взвешенного мулътиграфа С в тах{Д(С), г](С')} Цветов за время 0(гг2Д3). Относительная погрешность такого алгоритма меньше 2.

В неориентированном случае множество весов всех рёбер обозначим через IV = {и;1,гУ2, • • •, и^}, где > гог > • • • > ЭДь При любом г = 1,2,..., к через Е{ обозначается подмножество дуг, веса

которых не меньше г^. Рассматриваеся мультиграф С{ = (К, Ег), индуцированный рёбрами веса не менее ги¡. Пусть 1(0) = тах{Ш( + [Д(^)/21 | г - 1,2,..., к} и г(б) = та| г = 1, 2,..., к}. Доказана

Теорема 20. Пусть С = (У,Е) — неориентированный взвешенный мультиграф. Тогда 1(С) < ^ Г{С)-

2. (/с, I)-раскраска инциденторов. Пусть заданы такие целые числа к, I, что 0 < к <1. Правильная раскраска инциденторов называется (к, I)-раскраской, если разность цветов конечного и начального инциденторов каждой дуги принадлежит интервалу /]. Наименьшее число цветов, необходимое для (к, I)-раскраски инциденторов мультиграфа С, называется (к, I)-хроматическим числом и обозначаете через Хк,1(@)- Так в случае к = I = 0 имеем обычную задачу рёберной раскраски мультиграфов, и хо,о(С) = х'(О) ~ это рёберное хроматическое число мультиграфа С. При I — оо по теореме 7 имеем Хк,оо(С) = тах{Д(С), А+(С) + к, Д~(Сг) + к}. Ясно, что Хк,ь{С>') > Хк,1+[(С) для любых к и I. Также рассматриваеся параметр Хк,1(&) — тах{ХА;,/(С!) | Д(С) = Д} равный наименьшему числу цветов, в которое можно раскрасить инциденторы любого мультиграфа степени Д. Основные результаты по (к,1)-раскраске инциденторов, доказанные в диссертации, перечислены ниже.

• Доказано, что ход(А) = Д (теорема 12; совместный результат с В. Г. Визингом и Л. С. Мельниковым).

• Для любого нечётного Д построена бесконечная серия примеров мультиграфов, (1,1)-хроматическое число которых равно Д + 2 (теорема 14).

• Для любого мультиграфа С = (V, Е) степени 4 справедливо неравенство Х1,1(&) < 5 (теорема 15).

• При любом к > 1 имеет место верхняя оценка Хк,к(^) < [ЗА/2] + к - 1 (теорема 16).

• Для любого к > 1 и I > [~Д/2] выполняется равенство Х£,/(Д) = Д + к (теорема 17).

3. Предписанная раскраска инциденторов. Пусть С — взвешенный ориентированный мультиграф. Считается, что каждому ин-цидентору I сопоставлено некоторое множество цветов Ь(г), называемое предписанием инцидентора г. Пусть / : Е —» Z+ — некоторая целочисленная функция на множестве дуг мультигра-фа. Предписание называется f-корректным, если для каждой дуги е = иу в Ь(и,е) и Ь(у,е) найдутся соответственно такие цвета «1 < «2 < ■ • • < а/(е) И < 02 < ■ • ■ < /3/(е)! чт0 а] < Рз Для всех 3 = 1,2,..., /"(е). Раскраска инциденторов называется предписанной, если смежные инциденторы окрашиваются различно, разность между цветами конечного и начального инциденторов каждой дуги не меньше её веса и каждый инцидентор окрашен в один из предписанных ему цветов. Доказана

Теорема 18. Пусть б = (У,Е) — мультиграф максимальной степени 3 с таким /-корректным предписанием, что для каждой дуги е Е Е выполняется неравенство /(е) > ги(е) + 3. Тогда существует предписанная раскраска инциденторов мультиграфа С.

В третьей главе представлены результаты автора по вершинной и рёберной раскраскам графов. Рассмотрены следующие задачи.

1. Интервальная раскраска (3,4)-бирегулярного графа. Правильная рёберная раскраска графа <3 называется интервальной, если при каждой вершине множество использованных цветов образует интервал. Эта задача (для двудольных графов) возникает при построении школьных расписаний без «окон». Концепция интервальной раскраски впервые предложена в [1]. Двудольный граф С = (А,В;Е) называется (а,(3)-бирегулярным, если каждая вершина из А имеет степень а, а каждая вершина из В — степень /5. Доказана

Теорема 21. Пусть С = (АиВ\Е) — (3, А)-бирегулярный двудольный граф, в котором существует кубический подграф, покрывающий множество В. Тогда С? допускает интервальную раскраску.

2. Поиск графов Эрдёша и Дирака. Граф С называется к-кри-тическим, если его хроматическое число равно к, но при удалении

любого ребра получившийся граф можно раскрасить в к — 1 цвет. Концепция ^-критических графов была предложена Г. Дираком в 1949 году. Известно, что при к = 2 единственным ^-критическим графом является полный двухвершинный граф, а 3-критическими графами являются только нечётные циклы. При к > 4 структура /с-критнческих графов весьма разнообразна, и для таких графов не известна хорошая характеризация. В связи с этим изучение структуры 4-критических графов представляет особый интерес.

В 1960 году Г. Дирак [13, 14] сформулировал гипотезу о существовании вершинно г-связных 4-критических графов при всех г > 4. Такие графы называем графами Дирака. В 1989 году П. Эр-дёш в работе [15] предположил существование г-ооднородных 4-критических графов при всех г > 3, отметив, что ему не известны такие графы при г > 6. Графы, удовлетворяющие этой гипотезе, называем графами Эрдёша. При некоторых чётных г удалось построить графы, подтверждающие сразу обе эти гипотезы, т. е. являющиеся одновременно графами Эрдёша и Дирака. Более того, найденные графы являются также вершинно-транзитивными.

Пусть о,о, Я],.... а/; — такие целые положительные числа, что 1 < ао < а\ < ... < а^ < |_п/2] ■ Граф (? = С(п; ао, а\, .. • , ад.) с множеством вершин = {1,2, ...,п} называется циркулянтом, если множество его рёбер Е = {г ] : \г — Л = ат (тос! п), т = 0,1,..., к}. Все циркулянты являются вершинно-транзитивными графами. Первый пример 6-однородного 6-связного 4-критического графа, построенный в [45], представлен в следующей теореме.

Теорема 22. Циркулянт О = С(157; 1, 8,14) является 6-одно-родным б-связным 4-критическим графом.

Рёбра циркулянта, порождённые параметром а*, называем аг-рёбрами. Говорим, что циркулянт правильный, если ао = 1 и (п, аг) — 1 при любом г = 1, 2,..., к, где (а, Ь) обозначает наибольший общий делитель чисел а и Ь. Множество рёбер правильного циркулянта разбивается на к+1 гамильтонов цикл, причём г-й цикл порождается «¿-ребрами, г — 0,1, ...,к. Такие циклы называются аг-циклами. При этом ао-цикл называется главным циклом циркулянта.

Если в правильном циркулянте С(п; 1,04,..., а^) «¿-цикл взять в качестве главного, то получится другое представление исходного циркулянта, как правило, с иными параметрами. Такие представ-

ления называются инверсиями циркулянта C(n; l,ai,..., a/0) для различных г, 1 < г < к. Параметры любой инверсии циркулянта можно выразить через функцию rn>a(b) = min{r > 0 | га = ±Ь (mod п)} со значениями в интервале (0, \п/2\), которая определена однозначно, если (n, а) = 1. Заметим, что если в качестве главного цикла правильного циркулянта выбрать ai-цикл, то получается инверсия с параметрами С(п; rnm (1), 1, гпт (02)» • • • > гщах (а-к))-Аналогичное утверждение верно и для всех остальных значений г, 2 < г < к. Правильный циркулянт C(n; l,ai,... называется нормальным, если п = 1 (mod 6), <ц = 2 (mod 3) и rn,ai(aj) = 2 (mod 3) для всех aj € Л и aj 6 Л U {1} \ {а,}. Важность класса нормальных циркулянтов раскрывается в следующей лемме.

Лемма 18. Если в нормальном циркулянте удалить любое ребро, то хроматическое число полученного графа равно 3.

Для построения 4-хроматических циркулянтов необходимо изучить свойства 3-раскрасок циркулянтов. Пусть С(щ 1, ai,..., ад.) — 3-хроматический циркулянт, и пусть /j € {1,2,3} — цвет вершины г в некоторой его правильной 3-раскраске, i = 1,2, ...,п. Продолжив последовательность цветов / в обоих направлениях по правилу fi+kn = fi Для всех целых к и г = 1,2, ...,п, получим п-периодическое бесконечное слово над алфавитом {1,2,3}, в котором fi ф fj при \i — j I 6 Ли {1}. Вершину г называем внешней, если fi—i ф fi+i, и внутренней в противном случае. Через ci, C2,..., cs обозначим внешние вершины, лежащие в отрезке [1, п]. Раскраска / (возможно неправильная) называется периодической, если fi ф ,/г+1 и cj+i — cj нечётно при всех i,j. Это означает, в частности, что в периодической раскраске число внутренних вершин между любыми двумя последовательными внешними вершинами четно.

Назовём 3-хроматический циркулянт C(n; l,ai,...,ajfc) периодическим, если любая его правильная 3-раскраска является периодической. В следующей лемме представлены достаточные условия для того, чтобы циркулянт был периодическим.

Лемма 20. Пусть G — С{щ l,ai,...,a— 3-хроматический циркулянт. Тогда он является периодическим, если выполняется хотя бы одно из следующих условий:

1) ар = aq + 3 при некоторых p и q\

2) ap + a,q — 2 = ar при некоторых p, q и r (возможно, p — q);

3) Op + aq = n — 3 при некоторых p и q (возможно, p = q)\

4) ap + aq + ar = n + 2 при некоторых p, q иг (возможно, какие-то из них совпадают).

С другой стороны, в диссертации доказан следующий критерий сущетвования правильной 3-периодической раскраски нормального циркулянта.

Лемма 24. Циркулянт G = С(п; 1, ах,..., а&) имеет правильную периодическую 3-раскраску тогда и только тогда, когда существует такое целое t > 0, что

1) Для каждого нечётного параметра а £ 1ао, oi, ■••, найдётся такое неотрицательное целое та < Г^р], 'что п > Qat + За — бтап > —п.

2) Для каждого чётного параметра a G {ао,аь ...,ад.} найдётся такое неотрицательное целое та < что 4п > 6at + За — 6тап > 2п.

Отсюда следует, что если параметры нормального циркулянта G = С(щ 1, ai,..., at) удовлетворяют одному из условий леммы 20, но не удовлетворяют условию леммы 24, то такой циркулянт является одновременно графом Эрдёша и Дирака степени 2к + 2. Этот факт позволяет применить компьютерные методы для поиска графов Эрдёша и Дирака в классе нормальных циркулянтов.

Пусть п = 1 (mod 6) и Нп — следующий вспомогательный граф. Число v € {2,3,..., (п —1)/2} является вершиной графа Нп тогда и только тогда, когда (п, v) = 1, v = 2 (mod 3) и гП)1,(1) = 2 (mod 3). Две вершины и и v графа Нп смежны в том и только том случае, когда тп и(у) = 2 (mod 3) и rn,v(u) = 2 (mod 3). Метод поиска базируется на следующей лемме.

Лемма 25. Циркулянт С(щ 1, а\, й2, ■.., а/,) правилен и нормален тогда и только тогда, когда числа й2, ..., ад. являются вершинами графа Нп и образуют в нём клику.

С помощью описанного выше метода были проверены (с использованием компьютера) все нормальные циркулянты с п вершинами для п < 50000. Найдено

• 2 графа (Эрдёша и Дирака) степени 6;

• 13 графов степени 8;

• 12 графов степени 10;

• 45 графов степени 12;

• 36 графов степени 14;

• 5 графов степени 16.

Эти результаты (кроме леммы 18 и теоремы 22) получены в соавторстве с А. А. Добрыниным и Л. С. Мельниковым.

3. Покрывающая вырожденность и хроматичесое число. Граф (7 называется т- вырожденным, если любой его непустой подграф содержит вершину степени не более т. Наименьшее т, при котором граф С является т-вырожденным, обозначается через с^п(С).

Понятие покрывающей вырожденности Ь(С) графа было введено в [11] как

Здесь 51, ¿>2, • • ■! являются подмножествами множества V, а через с1§п(5г) обозначено число вырожденности подграфа, индуцированного множеством 5{. Если положить 5'г = V для всех г = 1,2,..., к, то 1/(С) < с^п((7) + 1. Если же в качестве 5^ взять цветовые классы правильной раскраски графа С?, то получится разбиение множества V на 0-вырожденнные множества. Отсюда следует, что !/((?) < х((?). В [11] была высказана гипотеза, что для любого графа С7 справедливо равенство £((7) = х(^).

В диссертации построен первый пример такого графа С, что Ь(С) < х(С). Этот граф не является 3-хроматическим, но при этом множество его вершин можно разбить на три подмножества, объединение любых двух из которых образует лес (откуда сразу имеем

Ь((7) = тш{А;| 351,52,..., 5^ такие, что

Цв) < 3).

В четвёртой главе изучаются нумерации графов, т. е. такие раскраски вершин, при которых все вершины получают разные цвета (метки). Тип нумерации определяется ограничениями на метки соседних вершин. Рассмотрены следующие виды нумераций.

1. Предписанная радио-нумерация. Результаты получены в соавторстве с X. Бодлендером, X. Брусма, Ф. В. Фоминым и Г. Вё-гингером. Радио-нумерацией неориентированного графа С = (V, Е) называется такое назначение меток, при котором метки смежных вершин отличаются как минимум на 2. Эта задача возникает при назначении радиочастот для передатчиков, находящихся в одной области. Все назначаемые радиочастоты должны быть различны, и при этом частоты близко расположенных друг от друга передатчиков должны различаться существенно. Требуется минимизировать ширину спектра используемых частот, т. е. номер наибольшей метки. В диссертации рассматривается предписанный вариант задачи о назначении радиочастот, при котором некоторым вершинам заранее предписаны метки, которые нельзя менять. Формально, для некоторого подмножества У С У задано отображение V : V' —> удовлетворяющее условиям радио-нумерации. Требуется продолжить его на всё множество вершин графа, т. е. найти такую радио-нумерацию Ь : V —> что Ь(и) = Ь'(и) для всех и 6 V', минимизируя при этом номер максимальной метки, которую называем шириной спектра и обозначаем через 5. Очевидной нижней оценкой для ширины спектра является величина

М = тах{п, тах!/(и)}.

иеУ

Насколько сильно может отличаться ширина спектра от нижней оценки М? Оказывается, это зависит от обхвата (длины минимального цикла) графа С.

Теорема 24. Пусть на п-вершинном графе (7, п > 7, задано предписание Ь'. Тогда существует радио-нумерация С, продолжающая V, с шириной спектра

(а) 5 < 1(7М - 2)/3] для любого й]

(б) 5 < [(5М + 2)/3], если обхват С не лгенъше 4;

(в) 5 < М + 3, если обхват С не меньше 5.

Все указанные оценки неулучшаемы, причём последняя из них достигается даже для путей.

Также изучается случай ¿-вырожденных графов. Получены следующие результаты.

Теорема 25. Пусть С является Ь-вырожденным графом с предписанием V. Тогда предписание V можно продолжить на весь граф С с шириной спектра Б < М + (4 + \/3)£ + 1.

Лемма 28. Пусть С? = (V, Е) — Ь-вырожденный граф максимальной степени А с предписанием V на множестве вершин V' С V. Если число непомеченных вершин р = |У \ У'\ удовлетворяет неравенству р > 4Д(£ + 1), то Ь' можно продолжить до радио-нумерации всего графа С с шириной спектра М.

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

2. Суммируемые и целочисленно суммируемые графы. Для данного подмножества Б множества целых чисел 2 через £?(£) обозначаем граф, вершинами которого являются все числа из 5, а две вершины и и V смежны тогда и только тогда, когда и + V € £>. Граф (7 — (У,Е) называется целочисленно суммируемым, если С = 0(8) для некоторого множества 5 С 2. Если же при этом все метки из 5 положительны, то граф (7 называется суммируемым. Очевидно, что суммируемый граф должен содержать хотя бы одну изолированную вершину (вершину с наибольшей меткой). Целочисленно суммируемые графы могут быть связными. Суммируемые графы были введены Харари [16]. Он показал, что любой граф можно сделать суммируемым, добавив к нему некоторое количество изолированных вершин, причём их число не превосходит числа рёбер графа. Минимальное число изолированных вершин, добавление которых превращает граф б в суммируемый, называется числом суммируемости графа (? и обозначается через ст(С).

В работе [17] утверждается, что для полного двудольного графа Кт,п, гДе т > п > 2, сг(Кт,п) = ["(3п + т — 3)/2]. В диссертации данное утверждение опровергнуто и доказана

Теорема 26. Для полного двудольного графа Кт,п = (X, У; Е) при т > п > 2 имеет место формула о(Кт^п) — \к(п — 1)/2 +

тп/{к- 1)1, где к = г(1 + V(8т + п - 1)/(п - 1))/2].

В [19] выдвинута гипотеза о том, что каждое дерево является целочисленно суммируемым графом. В диссертации эта гипотеза доказана для подразбиений деревьев (теорема 27), т. е. для таких деревьев, в которых никакие две развилки (вершины, степень которых не равна 2) несмежны.

Также построены две бесконечные серии унициклических графов, не являющихся целочисленно суммируемыми (теоремы 28 и 29) Доказано, что

а) любой однородный граф степени 2, кроме С, целочисленно суммируем (теорема 30);

б) для любого целого г > 3 существует однородный целочисленно суммируемый граф степени г (теорема 31).

Последние два результата получены совместно с Л. С. Мельниковым.

3. Графы представимые в виде слов. Результаты получены совместно с С. В. Китаевым и М. Халлдорссоном. Говорим, что слово ]¥ представляет граф С?, если для любых двух вершин х и у ребро ху существует тогда и только тогда, когда буквы х и у чередуются в V/ (другими словами, подслово, индуцированное этими буквами, не содержит в качестве фактора ни хх, ни уу). Граф С называется представимым, если существует слово И7, которое его представляет. Если С представим ^-униформным словом, то С? называется к-представимым. Доказана

Теорема 32. Граф О представим тогда и только тогда, когда он к-представим для некоторого к.

Числом представимости графа й назовём наименьшее натуральное к, для которого С будет к-представимым.

Назовём граф перестановочно представимым, если его можно представить словом вида Р1Р2 ■ ■ • Рк, где каждая из Р{, г — 1,1,..., к является перестановкой.

В работе [18] было доказано, что граф перестановочно представим тогда и только тогда, когда он является графом сравнимости, т. е. допускает транзитивную ориентацию. Следующая лем-

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

Лемма 31. Пусть х € ^((7) — вершина степени п — 1 и Н = С \ {ж}. Тогда С представим тогда только тогда, когда Н перестановочно представим.

Следствие 7. Если С представим, то для любой вершины х £ граф, индуцированный множеством её соседей N(x),

является графом сравнимости.

Заметим, однако, что условие следствия 7 не является достаточным для представимости графа С. Более того, как доказано в теореме 34, существует бесконечно много непредставимых графов без треугольников.

Найдена характеризация представимых графов через ориентации. Ориентированный граф С = (V, Е) назывется полутранзитивным, если он ациклический и для любого ориентированного пути и\У2--Ук либо УхУк Е, либо ViVj € Е для всех 1 < г < ] < к. Граф называется полутранзитивно ориентируемым, если он имеет полутранзитивную ориентацию. Справедлива следующая

Теорема 33. Граф представим тогда и только тогда, когда он полутранзитивно ориентируем.

Следствие 8. Любой 3-окрашиваемый граф являет,ся предст,а-вимым.

Из доказательства теоремы 33 можно вывести, что любой пред-ставимый граф тг-представим (откуда в частности следует, что задача распознавания представимых графов лежит в классе КР). Оказывается, существуют п-вершинные графы, число представимости каждого из которых равно [п/2]. Обозначим через Н^. граф, получаемый из полного двудольного графа К^.н удалением совершенного паросочетания. Пусть С^ получается из Н^ ь добавлением всесмежной вершины. Доказана

Теорема 35. Число представимости графа равно к = [п/2].

Следствие 9. Задача распознавания к-представимости графа является NP-полной при 3 < к < [п/2].

Заметим, что граф является 2-представимым тогда и только тогда, когда он является графом пересечений хорд. Доказано, что любой внешнепланарный граф является 2-представимым (теорема 36).

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

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

Получены следующие результаты (первый и второй в соавторстве с Ф. Грандони, А. А. Степановым и Ф. В. Фоминым, а третий и четвёртый — с С. Гасперсом, И. Разгоном и Ф. В. Фоминым).

• Граф с п вершинами содержит не более (1, 7170)" минимальных доминирующих множеств (следствие 10).

• Доматическое число n-вершинного графа G вычисляется за время 0{2,8718)" (теорема 38).

• Максимальный по мощности индуцированный лес в п-вершин-ном графе может быть найден за время 0(( 1,7548)") (теорема 39).

• Граф с п вершинами содержит не более (1,8638)" максимальных по включению индуцированных лесов (теорема 40).

Список литературы

[1] Асратян А. С., Камалян Р. Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. Вып. 5. Ереван: Изд-во Ереван, ун-та, 1987. С. 25-34.

[2] Визинг В. Г. Раскраска инциденторов мультиграфа в предписанные цвета // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 1. С. 32-39.

[3] Визинг В. Г. Раскраска инциденторов и вершин ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 3. С. 6-16.

[4] Визинг В. Г. Интервальная раскраска инциденторов ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 2. С. 40-51.

[5] Визинг В. Г. Интервальная раскраска инциденторов неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 1. С. 14-40.

[6] Визинг В. Г. Жёсткая раскраска инциденторов в неориентированных мультиграфах // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 3. С. 48-53.

[7] Визинг В. Г. О (р, д)-раскраске инциденторов неориснт.иро-ванного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 4. С. 23-39.

[8] Визинг В. Г. О раскраске инциденторов в гиперграфе // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 3. С. 40 45.

[9] Визинг В. Г. О раскраске инциденторов в частично ориентированном мультиграфе // Дискрет, анализ и исслед. операций. 2008. Т. 15. № 1. С. 17-22.

[10] Визинг В. Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 3. С. 3-14.

11] Amit A., Linian N., Matousek J. Random lifts of graphs III. Independence and chromatic number // Random Structures & Algorithms, 2002. V. 20. № 1. R 1-22.

12] Bansal N., Mahdian M., Sviridenko M. Minimizing makespan in no-wait job shops // Mathematics of Operations Research. 2006. V. 30. № 4. P. 817-831.

13] Dirac G. A. 4-chrome Graphen Trennende und vollständige A-Graphen // Math. Nachr. 1960. V. 22. № 1-2. P. 51-60.

14] Dirac G. A. In abstrakten Graphen vorhandene vollständige A-Graphen und ihre Unterteilungen // Math. Nachr. 1960. V. 22. № 1-2. P. 61-85.

15] Erdös P. On some aspects of my work with Gabriel Dirac // Graph Theory in Memory of G. A. Dirac. Amsterdam: North-Holland,

1989. P. 111-116. (Annals of Discrete Mathematics, V. 41).

16] Harary F. Sum graphs and difference graphs // Congr. Numer.

1990. V. 72. P. 101-108.

17] Hartsfield N., Smyth W. F. The sum number of complete bipartite graphs // Graphs, Matrices and Designs. New York: Marcel Dekker. 1993. P. 205-211.

18] Kitaev S. V., Seif S. Word problem of the Perkins semigroup via directed acyclic graphs // Order. 2008. V. 25. № 3. P. 177-194.

19] Liaw S.-C., Kuo D., Chang G. Integral sum numbers of graphs // Ars Combinatoria. 2000. V. 54. P. 259-268.

20] Melnikov L. S., Vizing V. G. The edge-chromatic number of a directed/mixed multigraph //J. Graph Theory. 1999. V. 23. № 4. P. 267-273.

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

Статьи в журналах

[21] Визинг В. Г., Мельников J1. С., Пяткин А. В. О (к, I)-раскраске инциденторов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 4. С. 29-37.

[22] Визинг В. Г., Пяткин А. В. О раскраске инциденторов в ориентированном взвешенном мультиграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 1. С. 33-44.

[23] Визинг В. Г., Пяткин А. В. Об оценках инциденторного хроматического числа взвешенного неориентированного мулъти-графа // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 2. С. 3-15.

Pyatkin А. V., Vizing V. G. Bounds for the incidentor chromatic number of a weighted undirected multigraph // Journal of Applied and Industrial Math. 2008. V. 2. № 3. P. 432-439.

[24] Добрынин А. А., Мельников JI. С., Пяткин А. В. Критические графы Эрдёша и Дирака четной степени // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 12-22.

[25] Плеханова Н. С., Пяткин А. В. Передача сообщений в локальной сети с двумя центральнъши ЭВМ // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 2. С. 91-99.

[26] Пяткин А. В. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи // Дискрет, анализ и исслед. операций. 1995. Т. 2. № 4. С. 74-79.

Pyatkin А. V. Some optimization problems of scheduling the transmission of messages in a local communication network // A. D. Korshunov (ed.), Operations Research and Discrete Analysis. Netherlands: Kluwer Academic Publishers. 1997. P. 227-232.

[27] Пяткин А. В. (к, I)-раскраска инцидепторов кубических мулъ-тиграфов // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 1. С. 49-53.

[28] Пяткин А. В. Некоторые верхние оценки для инциденторного (k, I)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 66-78.

[29] Пяткин А. В. Верхние и нижние оценки для инциденторного (k, I)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 1. С. 93-102.

[30] Пяткин А. В. Об (1,1)-раскраске инцидепторов мулыпиграфов степени 4 // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 3. С. 59-62.

[31] Пяткин А. В. Унициклические целочисленно несуммируемые графы // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 2. С. 16-24.

Pyatkin А. V. Unicyclic nonintegral sum graphs // J. of Applied and Industrial Math. 2008. V. 2. № 3. P. 379-384.

[32] Пяткин А. В. О предписанной раскраске инцидепторов в муль-тиграфе степени 3 // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 3. С. 80-89.

Pyatkin А. V. On list incidentor coloring of a multigraph of degree 3 // J. of Applied and Industrial Math. 2008. V. 2. № 4. P. 560-565.

[33] Bodlaender H. L., Broersma H., Fomin F. V., Pyatkin A. V., Woeginger G. J. Radio labeling with preassigned frequencies // SIAM J. of Optimization. 2004. V. 15. № 1. P. 1-16.

[34] Dobrynin A. A., Melnikov L. S., Pyatkin A. V. On 4-chromatic edge-critical regular graphs of high connectivity // Discrete Math. 2003. V. 260. N.l-3. P. 315-319.

[35] Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Regular 4-critical graphs of even degree // J. of Graph Theory. 2004. V. 46. № 2. P. 103-130.

[36] Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Erdos regular graphs of even degree // Discussiones Mathematicae Graph Theory. 2007. V. 27. № 2. P. 269-279.

[37] Fomin F. V., Gaspers S., Pyatkin A. V., Razgon I. On the minimum feedback vertex set problem: exact and enumeration algorithms // Algorit.hmica, 2008. V. 52. № 2. P. 293-307.

[38] Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications // ACM Transactions on Algorithms (TALG). 2008. V. 5. № 1. P. 9:1-9:17.

[39] Kitaev S. V., Pyatkin A. V. On representable graphs // Journal of Automata, Languages and Combinatorics, 2008. V. 13. № 1. P. 4554.

[40] Melnikov L. S. , Pyatkin A. V. Regular integral sum graphs // Discrete Math. 2002. V. 252. № 1-3. P. 237-245.

[41] Pyatkin A. V. Proof of Melnikov- Vizing conjecture for multigraphs with maximum degree at most 3// Discrete Math. 1998. V. 185. № 1-3. P. 275-278.

[42] Pyatkin A. V. New formula for the sum number for the complete biparitite graphs // Discrete Math. 2001. V. 239. № 1-3. P. 155-160.

[43] Pyatkin A. V. A graph with cover degeneracy less than chromatic number 11 J. of Graph Theory. 2001. V. 37. № 4. P. 243-246.

[44] Pyatkin A. V. The incidentor coloring of multigraphs and its applications // Discrete Applied Math. 2002. V. 120. № 1-3. P. 209217.

[45] Pyatkin A. V. 6-regular A-critical graph // J. of Graph Theory. 2002. V. 41. № 4. P. 286-291.

[46] Pyatkin A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs // J. of Graph Theory. 2004. V. 47. № 2. P. 122-128.

[47] Pyatkin A. V. Subdivided trees are integral sum graphs // Discrete Math. 2008. V. 308. № 9. P. 1749-1750.

Прочие публикации

[48] Визинг В. Г., Мельников J1. С., Пяткин А. В. О (к, 1)-раскраске инциденторов // Международная конференция «Дискретный анализ и исследование операций» (DAOR-2000). Материалы конференции. Новосибирск, 2000. С. 94.

[49] Визинг В. Г., Пяткин А. В. Задача раскраски инциденторов мулътиграфа // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 6-11.

[50] Добрынин А. А., Мельников J1. С., Пяткин А. В.

4-хроматические реберно-критические регулярные графы с высокой связностью // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Новосибирск, 2002. С. 25-30.

[51] Пяткин А. В. Задачи поиска оптимального расписания передачи данных в локальной сети связи // Второй Сибирский конгресс по прикладной и индустриальной математике (INPRIM-96). Тезисы докладов. Новосибирск, 1996. С. 141.

[52] Пяткин А. В. Задача окраски инциденторов //IX межгосударственная школа-семинар «Синтез и сложность управляющих систем». Тезисы докладов. Нижний Новгород, 1998. С. 72.

[53] Пяткин А. В. О раскраске инциденторов и их применении в теории графов // Конференция молодых ученых, посвященная 100-летию М. А. Лаврентьева. Материалы конференции. Новосибирск, 2000. С. 27-28.

[54] Пяткин А. В. (k, I)-раскраска инциденторов и применение инциденторов в теории графов / / Конференция молодых ученых по математике, математическому моделированию и информатике. Материалы конференции. Новосибирск, 2001. С. 13-14.

[55] Пяткин А. В. Некоторые оценки для максимального числа цветов в (k, I)-раскраске инциденторов // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск;, 2002. С. 149.

[56] Пяткин А. В. Получение оценок для инциденторного (k,l)-хроматического числа // Материалы III конференции молодых учёных, посвященной М. А. Лаврентьеву. Новосибирск, 2003. С. 44-47.

[57] Пяткин А. В. (k, I)-раскраска инциденторов: некоторые результаты // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 114.

[58] Bodlaender Н. L., Broersma Н., Fomin F. V., Pyatkin А. V., Woeginger G. J. Radio labeling with pre-assigned frequencies // ESA 2002: 10th Annual European symposium on algorithms. Berlin: Springer-Verlag, 2002. P. 211-222. (Lecture Notes in Computer Sci. V. 2461).

[59] Fomin F. V., Gaspers S., Pyatkin A. V. Finding minimum feedback vertex set in time 0((l,7548)n) // Report № 324, Department of Informatics, University of Bergen, 2006. P. 1-7.

[60] Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. On maximum number of minimal dominating sets in graphs / / Electronic Notes in Discrete Mathematics. 2005. V. 22. P. 157-162.

[61] Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. Bounding the number of minimal dominating sets: a measure and conquer approach // ISAAC 2005: 16th International symposium on algorithms and computation. Berlin: Springer, 2005. P. 574-582. (Lecture Notes in Computer Science. V. 3827.)

[62] Fomin F. V., Pyatkin A. V. Finding minimum feedback vertex set in bipartite graph // Report № 291, Department of Informatics, University of Bergen, 2005. P. 1-7.

[63] Halldorson M., Kitaev S. V., Pyatkin A. V. On representable graphs, semi-transitive orientations, and the representation numbers // http://arxiv.org/abs/0810.0310.

[64] Kitaev S. V., Pyatkin A. V. On representable graphs // Report № 312, Department of Informatics, University of Bergen, 2005. P. 1-8.

[65] Pyatkin A. V. The incidentor coloring of multigraphs and its application in data networks // Extended Abstracts of the 6th Twente workshop on graphs and combinatorial optimization. Netherlands, 1999. P. 197-200.

[66] Pyatkin A. V. Results on (k, I)-coloring of incidentors // Proceedings of 8th Nordic combinatorial conference. Aalborg, Denmark, 2004. P. 83-86.

[67] Pyatkin A. V., Vizing V. G. Incidentor coloring of weighted multigraph // Electronic Notes in Discrete Mathematics. 2006. V. 27. P. 103-104.

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

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

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

Подписано в печать 12.05.09. Формат 60x84 1/16. Усл. печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 120 экз. Заказ № 83.

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск

Введение

Глава 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 Дирака чётной степени г,

4 < г < 16.

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. Оценка для числа максимальных по включению индуцированных лесов.

Характерной особенностью дискретной математики является то, что в этой области многие доказательства являются конструктивными, позволяющими непосредственно построить искомый объект или выделить его часть, обладающую некоторыми интересными с точки зрения исследователя свойствами. Возможно это связано с тем, что большинство задач дискретной математики возникло из приложений, где требуется не только доказать возможность достижения цели, но и предъявить алгоритм, позволяющий это сделать. Так называемые «теоремы существования», которые только доказывают, что объект существует, но не дают при этом никаких идей, как его можно построить, встречаются в дискретной математике довольно редко. И даже если такие теоремы появляются, то исследователи, как правило, продолжают работать над поиском конструктивных доказательств. Классическим примером вышесказанного может служить знаменитая теорема Эрдёша 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 наименований.

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

2. Визинг В. Г. Раскраска инциденторов мультиграфа в предписанные цвета // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 1. С. 32-39.

3. Визинг В. Г. Раскраска инциденторов и вершин ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 3. С. 6-16.

4. Визинг В. Г. Интервальная раскраска инциденторов ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 2. С. 40-51.

5. Визинг В. Г. Двудольная интерпретация ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 1. С. 27-41.

6. Визинг В. Г. Интервальная раскраска инциденторов неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 1. С. 14-40.

7. Визинг В. Г. О линейных факторах мультиграфов // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 4. С. 3-7.

8. Визинг В. Г. Факторная раскраска ребер мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 2. С. 18—31.

9. Визинг В. Г. Жёсткая раскраска инциденторов в неориентированных мулътиграфах // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 3. С. 48-53.

10. Визинг В. Г. О (р, -раскраске инциденторов неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 4. С. 23—39.

11. Визинг В. Г. Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 4. С. 18-25.

12. Визинг В. Г. О раскраске инциденторов в гиперграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 3. С. 40-45.

13. Визинг В. Г. О раскраске инциденторов в частично ориентированном мультиграфе // Дискрет, анализ и исслед. операций. 2008. Т. 15. № 1. С. 17-22.

14. Визинг В. Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 3. С. 3-14.

15. Витавер Л. М. Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежности // Докл. АН СССР, 1962. Т. 147. № 4. С. 758-759.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

17. Дистель Р. Теория графов. Новосибирск. Изд-во Института математики, 2002.

18. Дольников В. Л. Трансверсали семейств множеств в Мп и связь между теоремами Хелли и Борсука // Матем. сб., 1993. Т. 184. № 5. С. 111-132.

19. Евстигнеев В. А., Мельников JL С. Задачи и упражнения по теории графов и комбинаторике. Новосибирск: НГУ, 1981.

20. Севастьянов С. В. Об интервальной раскрашиваемости ребер двудольного графа // Методы дискретного анализа. Вып 50. Новосибирск, 1990. С. 61-72.

21. Amit A., Linian N., Matousek J. Random lifts of graphs III: Independence and chromatic number / / Random Structures &; Algorithms, 2002. V. 20. № 1. P. 1-22.

22. Asratian A. S., Casselgren C. J. On interval edge colorings of (a,{3)~ biregular bipartite graphs // Discrete Math., 2007. V. 307. № 15. P. 19511956.

23. Asratian A. S., Casselgren C. J. On path factors of (3,4)-biregular bigraphs // Graphs & Combinatorics, 2008. V. 24. P. 405-411.

24. Asratian A. S., Casselgren C. J., Vandenbussche J., West D. B. Proper path-factors and interval edge-coloring of (3,4:)-biregular bigraphs //J. Graph Theory (to appear).

25. Asratian A. S., Kamalian R. R. Investigation on interval edge-coloring of graphs // J. of Combinatorial Theory. Ser. B. 1994. V. 62. № 1. P. 34-43.

26. Bafna V., Berman P., Fujito Т. A 2-approximation algorithm for the undirected feedback vertex set problem // SIAM J. on Discrete Math., 1999. V. 12. № 3. P. 289-297.

27. Bansal N., Mahdian M., Sviridenko M. Minimizing makespan in no-wait job shops // Mathematics of Operations Research. 2006. V. 30. № 4. P. 817-831.

28. Barany I. A short proof of Knes er's conjecture //J. Combin. Theory. Ser. A. 1978. V. 25. № 3. P. 325-326.

29. Bodlaender H. L., Kloks T., Tan R. B., van Leeuwen J. A-coloring of graphs // STACS 2000: 17th annual symposium on theoretical aspects of computer science. Proc. Berlin: Springer, 2000. P. 395-406. (Lecture Notes in Computer Sei. V. 1770).

30. Brooks R. L. On coloring the nodes of a network // Proc. Cambridge Phil. Soc. 1941. V. 37. P. 194-197.

31. Brualdi R. A., Massey J. J. Q. Incidence and strong edge coloring of graphs // Discrete Math. 1993. V. 122. № 1-3. P. 51-58.

32. Chang G. J., Kuo D. The L(2,1 )-labeling problem on graphs // SIAM J. Discrete Math. 1996. V. 9. № 2. P. 309-316.

33. Chen Z. Integral sum graphs from identification// Discrete Math. 1998. V. 181. № 1-3. P. 77-90.

34. Damaschke P., Deogun J. S., Kratsch D., Steiner G. Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm // Order. 1992. V. 8. № 4. P. 383-391.

35. Dirac G. A. 4-chrome Graphen Trennende und vollständige A-Graphen // Math. Nachr. 1960. V. 22. № 1-2. P. 51-60.

36. Dirac G. A. In abstrakten Graphen vorhandene vollständige A-Graphen und ihre Unterteilungen // Math. Nachr. 1960. V. 22. № 1-2. P. 61-85.

37. Dolama M. H., Sopena E., Zhu X. Incidence coloring of k-degenera,te graphs // Discrete Math. 2004. V. 283. № 1-3. P. 121-128.

38. Erdös P. Graph theory and probability // Canad. J. Math. 1959. V. 11. P. 34-38.

39. Erdos P. On some aspects of my work with Gabriel Dirac // Graph Theory in Memory of G. A. Dirac. Amsterdam: North-Holland, 1989. P. 111-116. (Annals of Discrete Mathematics, V. 41).

40. Gabor C. P., Supowit K. J., Hsu W.-L. Recognizing circle graphs in polynomial time // J. of the ACM. 1989. V. 36. № 3. P. 435-473.

41. Gallai T. Kritische Graphen I. // Publ. Math. Inst. Hungar. Acad. Sci. 1963. V. 8. № 1-2. P. 165-192.

42. Gallian J. A. A dynamic survey of graph labeling http://www.combinatorics.org/Surveys/ds6.pdf

43. Graham R., Zang N. Enumerating split-pair arrangements //J. Combin. Theory. Ser. A. 2008. V. 115. № 2. P. 293-303.

44. Guiduli B. On incidence coloring and star arboricity of graphs // Discrete Math. 1997. V. 163. № 1-3. P. 275-278.

45. Hanson D., Loten C. O. M., Toft B. On interval colorings of bi-regular bipartite graphs // Ars Combinatoria. 1998. V. 50. P. 23-32.

46. Harary F. Sum graphs and difference graphs // Congr. Numer. 1990. V. 72. P. 101-108.

47. Harary F. Sum graphs over all integers // Discrete Math. 1994. V. 124. № 1-3. P. 99-105.

48. Hartsfield N., Smyth W. F. The sum number of complete bipartite graphs // Graphs, Matrices and Designs. New York: Marcel Dekker. 1993. P. 205211.

49. He W., Wang L., Mi H., Shen Y., Yu X. Integral sum graphs from a class of tree // Ars Combinatoria, 2004. V. 70. P. 197-205.

50. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. 1981. V. 10. № 4. P. 718-720.

51. Jensen T. R. Dense critical and vertex-critical graphs // Discrete Math. 2002. V. 258. № 1-3. P. 63-84.

52. Jensen T. R., Royle G. F. Small graphs of chromatic number 5: a computer search // J. Graph Theory. 1995. V. 19. № 1. P. 107-116.

53. Jensen T. R., Toft B. Graph coloring problems. New York: John Wiley & Sons. 1995.

54. Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. New York: Plenum Press, 1972. P. 85-103.

55. Kitaev S. V., Seif S. Word problem of the Perkins semigroup via directed acyclic graphs // Order. 2008. V. 25. № 3. P. 177-194.

56. Kneser M. Aufgabe 360 // Jahresbericht der Deutschen MathematikerVereinigung, 1955. V. 2. № 58. P. 27.

57. König D. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Math. Ann. 1916. V. 77. P. 453-465.

58. Koester G. Note to a problem of T. Gallai and G. A. Dirac // Combinatorica. 1985. V. 5. № 3. P. 227-228.

59. Koester G. 4-critical 4-valent planar graphs constructed with crowns // Math. Scand. 1990. V. 67. P. 15-22.

60. Lawler E. L. A note on the complexity of the chromatic number problem // Information Processing Letters. 1976. V. 5. № 3. P. 66-67.

61. Lenstra J. K., Hoogeveen H., Yu W. Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard // J. of Scheduling, 2004. V. 7. № 5. P. 333-348.

62. Li D., Liu M. Incidence coloring of the squares of some graphs // Discrete Math. 2008. V. 308. № 22. P. 6569-6574.

63. Liaw S.-C., Kuo D., Chang G. Integral sum numbers of graphs // Ars Combinatoria. 2000. V. 54. P. 259-268.

64. Lothaire M. Algebraic Combinatorics on Words. Cambridge, UK: Cambridge University Press, 2001.

65. Lovasz L. On chromatic number of finite set-systems // Acta Math. Acad. Sei. Hungar. 1968. V. 19. P. 59-67.

66. Lovasz L. Kneser's conjecture, chromatic number and homotopy // J. Combin. Theory. Ser. A, 1978. V. 25. № 3. P. 319-324.

67. Lovasz L., Plummer M. D. Matching theory. Budapest: Akademiai Kiado, 1986.

68. Lubotzky A., Philips R., Sarnak P. Ramanujan graphs // Combinatorica, 1988. V. 8. P. 261-277.

69. Mader W. Über den Zusammenhäng symmetrischer Graphen // Arch. Math. (Basel). 1970. V. 21. N. 3. P. 331-336.

70. Mader W. Eine Eigenschaft der Atome endlicher Graphen // Arch. Math. (Basel). 1971. V. 22. № 3. P. 333-336.

71. Matousek J. A combinatorial proof of Kneser's conjecture // Combinatorica, 2004. V. 24. № 1. P. 163-170.

72. Melnikov L. S., Vizing V. G. The edge-chromatic number of a directed/mixed multigraph //J. Graph Theory. 1999. V. 23. № 4. P. 267273.

73. Moon J. W., Moser L. On cliques in graphs // Israel J. of Mathematics. 1965. V. 3. P. 23-28.

74. Nesetril J., Rödl V. A short proof of the existence of highly chromatic hypergraphs without short cycles //J. Combin. Theory. Ser. B. 1979. V. 27. № 2. P. 225-227.

75. Nicholas T., Somasimdaram S. More results on integral sum graphs // Proc. of National Conference on Graph Theory and its Applications, Chennai. 2001.

76. Petersen J. Die theorie der regulären graphen // Acta Math. 1891. V. 15. P. 193-220.

77. Razgon I. Exact computation of maximum induced forest // SWAT 2006: 10th Scandinavian workshop on algorithm theory. Berlin: Springer-Verlag, 2006. P. 160-171. (Lecture Notes in Comput. Science. V. 4059)

78. Ringel G. Färbungsprobleme auf Flächen und Graphen. VEB Deutscher Verlag der Wissenschaphten, 1959.

79. Robson J. M. Algorithms for maximum independent sets // J. of Algorithms. 1986. V. 7. № 3. P. 425-440.

80. Sakai D. Labeling chordal graphs: distance two condition // SIAM J. Discrete Math., 1994. V. 7. № 1. P. 133-140.

81. Sarkaria K. S. A generalized Kneser conjecture // J. Combin. Theory. Ser. B. 1990. V. 49. № 2. P. 236-240.

82. Schwikowski B., Speckenmeyer E. On enumerating all minimal solutions of feedback problems // Discrete Applied Math. 2002. V. 117. № 1-3. P. 253-265.

83. Seif S. The Perkins semigroup has co-NP-complete term-equivalence problem // Internat. J. Algebra Comput. 2005. V. 15. № 2. P 317-326.

84. Shannon C. E. A theorem on coloring the lines of a networks //J. Math. Phys., 1949. V. 28, P. 148-151.

85. Sharary A. Integral sum graphs from complete graphs, cycles and wheelsH Arab Gulf J- Scient. Res. 1996. V. 14. № 1. P. 1-14.

86. Shiu W. C., Sun P. K. Invalid poofs on incidence coloring // Discrete Math. 2008. V. 308. № 22. P. 6575-6580.

87. Tarjan R. E., Trojanowski A. E. Finding a maximum independent set // SIAM J. on Computing. 1977. V. 6. № 3. P. 537-546.

88. Watkins M. E. Some classes of hypoconnected vertex-transitive graphs !/ Recent Progress in Combinatorics. New York: Academic Press, 1969. P. 323-328.

89. Watkins M. E. Connectivity of transitive graphs //J. Combin. Theory. 1970. V. 8. № 1. P. 23-29.

90. Woeginger G. Exact algorithms for NP-hard problems: A survey // Combinatorial optimization. 5th international workshop. Berlin: Springer, 2003. P. 185-207. ( Lecture Notes in Comput. Science. V. 2570.)

91. Wu J., Mao J., Li D. New types of integral sum graphs // Discrete Math. 2003. V. 260. № 1-3. P. 163-176.

92. Xu B. On integral sum graphs// Discrete Math. 1999. V. 194. № 1-3. P. 285-294.

93. Yannakakis M. The complexity of the partial order dimension problem // SIAM J. Algebraic Discrete Methods. 1982. V. 3 № 3. P. 351-358.

94. Youngs D. A. Gallai's problem on Dime's construction // Discrete Math. 1992. V. 101. № 1-3. P. 343-350.Публикации автора по теме диссертации Статьи в журналах

95. Визинг В. Г., Мельников JI. С., Пяткин А. В. О (к, I)-раскраске ии-циденторов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 4. С. 29-37.

96. Визинг В. Г., Пяткин А. В. О раскраске инцидепторов в ориентированном взвешенном мультиграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 1. С. 33-44.

97. Добрынин А. А., Мельников JI. С., Пяткин А. В. Критические графы Эрдёша и Дирака четной степени // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 12-22.

98. Плеханова H. С., Пяткин А. В. Передача сообщений в локальной сети с двумя центральными ЭВМ // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 2. С. 91-99.

99. Пяткин А. В. (k, l)-раскраска инциденторов кубических мульти-графов ¡I Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 1. С. 49-53.

100. Пяткин А. В. Некоторые верхние оценки для инциденторного (k, I)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 66-78.

101. Пяткин А. В. Верхние и нижние оценки для инциденторного (к, /)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 1. С. 93-102.

102. Пяткин А. В. Об (1,1)-раскраске инциденторов мультиграфов степени 4 // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 3. С. 59-62.

103. Пяткин А. В. Унициклические целочисленно несуммируемые графы II Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 2. С. 16-24.Pyatkin А. V. Unicyclic nonintegral sum graphs // J. of Applied and Industrial Math. 2008. V. 2. № 3. P. 379-384.

104. Bodlaender H. L., Broersma H., Fomin F. V., Pyatkin A. V., Woeginger G. J. Radio labeling with preassigned frequencies // SIAM J. of Optimization. 2004. V. 15. № 1. P. 1-16.

105. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. On 4-chromatic edge-critical regular graphs of high connectivity // Discrete Math. 2003. V. 260. № 1-3. P. 315-319.

106. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Regular 4-critical graphs of even degree // J. of Graph Theory. 2004. V. 46. № 2. P. 103-130.

107. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Erdos regular graphs of even degree // Discussiones Mathematicae Graph Theory. 2007. V. 27. № 2. P. 269-279.

108. Fomin F. V., Gaspers S., Pyatkin A. V., Razgon I. On the minimum feedback vertex set problem: exact and enumeration algorithms // Algorithmica, 2008. V. 52. № 2. P. 293-307.

109. Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications // ACM Transactions on Algorithms (TALG). 2008. V. 5. № 1. P. 9:1-9:17.

110. Kitaev S. V., Pyatkin A. V. On representable graphs // Journal of Automata, Languages and Combinatorics. 2008. V. 13. № 1. P. 45-54.

111. Melnikov L. S. , Pyatkin A. V. Regular integral sum graphs // Discrete Math. 2002. V. 252. № 1-3. P. 237-245.

112. Pyatkin A. V. Proof of Melnikov-Vizing conjecture for multigraphs with maximum degree at most 3// Discrete Math. 1998. V. 185. № 1-3. P. 275278.

113. Pyatkin A. V. New formula for the sum number for the complete biparitite graphs // Discrete Math. 2001. V. 239. № 1-3. P. 155-160.

114. Pyatkin A. V. A graph with cover degeneracy less than chromatic number // J. of Graph Theory. 2001. V. 37. № 4. P. 243-246.

115. Pyatkin A. V. The incidentor coloring of multigraphs and its applications // Discrete Applied Math. 2002. V. 120. № 1-3. P. 209-217.

116. Pyatkin A. V. 6-regular 4-critical graph // J. of Graph Theory. 2002. V. 41. № 4. P. 286-291.

117. Pyatkin A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs // J. of Graph Theory. 2004. V. 47. № 2. P. 122-128.

118. Pyatkin A. V. Subdivided trees are integral sum graphs // Discrete Math. 2008. V. 308. № 9. P. 1749-1750.Прочие публикации

119. Визинг В. Г., Мельников JI. С., Пяткин А. В. О (к, I)-раскраске инциденторов / / Международная конференция «Дискретный анализ и исследование операций» (DAOR-2000). Материалы конференции. Новосибирск, 2000. С. 94.

120. Визинг В. Г., Пяткин А. В. Задача раскраски инциденторов мулъ-тиграфа // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 6-11.

121. Добрынин А. А., Мельников Л. С., Пяткин А. В. 4-хроматические реберно-критические регулярные графы с высокой связностью // Российская конференция «Дискретный анализ и исследование операций» (БАОЯ-2002). Новосибирск, 2002. С. 25-30.

122. Пяткин А. В. Задачи поиска оптимального расписания передачи данных в локальной сети связи // Второй Сибирский конгресс по прикладной и индустриальной математике (ШРШМ-96). Тезисы докладов. Новосибирск, 1996. С. 141.

123. Пяткин А. В. Задача окраски инциденторов //IX межгосударственная школа-семинар «Синтез и сложность управляющих систем». Тезисы докладов. Нижний Новгород, 1998. С. 72.

124. Пяткин А. В. О раскраске инциденторов и их применении в теории графов // Конференция молодых ученых, посвященная 100-летию М. А. Лаврентьева. Материалы конференции. Новосибирск, 2000. С. 27-28.

125. Пяткин А. В. (к, I)-раскраска инциденторов и применение инциденторов в теории графов // Конференция молодых ученых по математике, математическому моделированию и информатике. Материалы конференции. Новосибирск, 2001. С. 13-14.

126. Пяткин А. В. Некоторые оценки для максимального числа цветов в (к, I)-раскраске инциденторов // Российская конференция «Дискретный анализ и исследование операций» (БА011-2002). Материалы конференции. Новосибирск, 2002. С. 149.

127. Пяткин А. В. Получение оценок для инциденторного (к,1)-хроматического числа // Материалы III конференции молодых учёных, посвящённой М. А. Лаврентьеву. Новосибирск, 2003. С. 44-47.

128. Пяткин А. В. (к, I)-раскраска инциденторов: некоторые результаты // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 114.

129. Fomin F. V., Gaspers S., Pyatkin A. V. Finding minimum feedback vertex set in time (9((1,7548)n) // Report № 324, Department of Informatics, University of Bergen, 2006. P. 1-7.

130. Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. On maximum number of minimal dominating sets in graphs // Electronic Notes in Discrete Mathematics. 2005. V. 22. P. 157-162.

131. Fomin F. V., Pyatkin A. V. Finding minimum feedback vertex set in bipartite graph // Report № 291, Department of Informatics, University of Bergen, 2005. P. 1-7.

132. Halldorson M., Kitaev S. V., Pyatkin A. V. On representable graphs, semi-transitive orientations, and the representation numbers // http://arxiv.org/abs/0810.0310

133. Kitaev S. V., Pyatkin A. V. On representable graphs // Report № 312, Department of Informatics, University of Bergen, 2005. P. 1-8.

134. Pyatkin A. V. The incidentor coloring of multigraphs and its application in data networks // Extended Abstracts of the 6th Twenteworkshop on graphs and combinatorial optimization. Netherlands, 1999. P. 197-200.

135. Pyatkin A. V. Results on (k, I)-coloring of incidentors // Proceedings of 8th Nordic combinatorial conference. Aalborg, Denmark, 2004. P. 8386.

136. Pyatkin A. V., Vizing V. G. Incidentor coloring of weighted multigraph // Electronic Notes in Discrete Mathematics. 2006. V. 27. P. 103-104.