авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Строение младших граней и (p, q)-раскраски плоских графов

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

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

Неустроева Татьяна Кимовна СТРОЕНИЕ МЛАДШИХ ГРАНЕЙ И (P, Q)-РАСКРАСКИ ПЛОСКИХ ГРАФОВ Специальность 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Новосибирск, 2007

Работа выполнена в Институте математики им. С. Л. Соболе ва СО РАН и НИИ математики при Якутском государственном университете.

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

Официальные оппоненты: доктор физико-математических наук А. Д. Коршунов, кандидат физико-математических наук В. А. Аксенов

Ведущая организация: Институт систем информатики СО РАН

Защита состоится “ 11 ” апреля 2007 г. в 16 часов на за седании диссертационного совета Д 003.015.01 в Институте ма тематики им. С. Л. Соболева СО РАН по адресу: пр. Коптюга 4, 630090, г. Новосибирск.

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

Автореферат разослан “ 9 ” марта 2007 г.

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

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

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

Наиболее широко известной из задач раскраски графов яв ляется знаменитая проблема четырех красок (1852 г.): требует ся доказать возможность раскрасить плоскую карту четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Доказательство было дано бо лее чем через 120 лет К. Аппелем и В. Хакеном. Решение со стояло в построении так называемой “неизбежной системы сво димых конфигураций”, а именно в нахождении такой системы структурных фрагментов, что хотя бы один из них содержится в каждом графе рассматриваемого класса, причем каждая из этих конфигураций является сводимой, т. е. должна отсутствовать в минимальном контрпримере к данной задаче о раскраске. Метод сводимых конфигураций применяется для решения подавляю щего большинства задач раскраски плоских графов. Наиболее полную информацию о результатах в области раскраски графов, полученных до середины 90-х годов прошлого столетия, можно найти в книге В. Тофта и Т. Р. Йенсена [7].

Отметим, что первоначально большинство фактов о строе нии плоских графов, установленных при решении задач о рас красках, использовались только в рамках рассматриваемой за дачи, т. е. интерес к локальным свойствам графов возникал толь ко применительно к задачам раскраски. Один из первых шагов в изучении структуры плоских графов был сделан А. Лебегом в 1940 г. Созданная А. Лебегом [9] теория эйлеровых вкладов, основанная на преобразовании известной формулы Эйлера для многогранников, в дальнейшем получила широкое применение и развитие в работах А. Коцига [8], Б. Грюнбаума [6] и других.

Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [1] – [5]. Перечисленные, а также и многие другие, работы по рас краскам плоских графов позволили теоремам о строении плос ких графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов.

Введение в эту теорию представлено в докторской диссертации О. В. Бородина [1].

Заметим, что структурные теоремы, полученные в перечис ленных выше работах, касаются плоских графов с минимальной степенью 3. Что же касается плоских графов с = 2, то, хотя об их строении известно довольно много, стройной клас сификации этих графов в настоящее время пока нет. Интерес к изучению строения плоских графов с = 2 вызван возмож ностью применения структурных свойств этих графов к некото рым видам раскраски графов, в частности, реберной, тотальной, 2-дистанционной, (p, q)-раскраске, ориентированной, предписан ной и других.

В диссертации рассматриваются (p, q)-раскраска и частный случай этого вида раскраски, 2-дистанционная, разреженных плоских графов (имеющих заданный обхват), при изучении ко торых мы сталкиваемся с графами, имеющими = 2.

Задача (p, q)-раскраски плоских графов является одной из основных моделей в проблеме распределения радиочастот в се тях мобильного телефонирования, когда источники (вершины плоского графа) должны получить целочисленные частоты (быть раскрашены) так, чтобы цвета вершин, расстояние между которыми равно 1, различались не менее чем на p, а на расстоя нии 2 не менее чем на q. Поскольку частоты близко располо женных источников должны различаться сильнее ввиду интер ференции волн, то p q.





Цель работы состоит в получении новых результатов о строении младших граней в 3-многогранниках и (p, q)-раскраске (в том числе и предписанной) разреженных плоских графов, причем в диссертации большое внимание уделяется наиболее важному частному случаю этой раскраски 2-дистанционной.



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

Научная новизна. Выделим основные результаты диссер тации.

1. Уточнен один из параметров теоремы Бородина (2002 г.), усиливающей теорему Лебега (1940 г.) о строении младших гра ней 3-многогранников.

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

опре деленное условие на обхват является неулучшаемым.

3. В дополнение к результатам п. 2, при g = 6 найден класс 2-дистанционно ( + 1)-раскрашиваемых плоских графов;

они имеют 31, а каждое ребро в них инцидентно вершине сте пени 2.

4. Для планарного графа G достаточно большого обхвата доказаны верхняя и нижняя оценки его (p, q)-хроматического числа (как предписанного, так и обычного), которые отличаются друг от друга на величину, не зависящую от p.

В диссертацию включены лишь те результаты совместных работ [12] – [20], которые получены диссертантом.

Теоретическая и практическая ценность. Результаты работы носят теоретический характер. Результаты о (p, q)-рас красках плоских графов в перспективе могут быть использова ны при решении проблемы распределения радиочастот в сетях мобильной связи.

Апробация работы. Результаты работы докладывались в 2006 г. на X Лаврентьевских чтениях Республики Саха (Якутия) и IV Всероссийской школе-семинаре студентов, аспирантов, мо лодых ученых и специалистов "Математическое моделирование развития северных территорий РФ"и подробно обсуждались на научном семинаре лаборатории теории графов Института ма тематики СО РАН в 2004–2006 гг. Работа автора по раскраске плоских графов в 2005–2007 гг. поддержана грантом РФФИ 05 01-00816. Автор в 2006 г. за работу по теме диссертации получил Государственную стипендию Республики Саха (Якутия) для мо лодых ученых и аспирантов.

Публикации. По теме диссертации опубликованы 9 работ (включая 7 журнальных статей и одну статью в трудах конфе ренции X Лаврентьевских чтений).

Структура и объем диссертации. Диссертация изложе на на 78 страницах и состоит из введения, трех глав и библио графии, содержащей 45 наименований.

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

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

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

Будем говорить, что грань f = v1,..., vr ранга r (длина гра ничного цикла грани) имеет тип (d1,..., dr ), где di di+1 при каждом i, 1 i r 1, если i-я по величине степень вер шины среди вершин, инцидентных грани f, не превосходит di, 1 i r.

В 1940 г. А. Лебег [9] показал, что любой 3-многогранник содержит грань одного из следующих типов:

(3, 6, ), (3, 7, 41), (3, 8, 23), (3, 9, 17), (3, 10, 14), (3, 11, 13), (4, 4, ), (4, 5, 19), (4, 6, 11), (4, 7, 9), (5, 5, 9), (5, 6, 7), (3, 3, 3, ), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5), (3, 3, 3, 3, 5).

Некоторые параметры этого описания позднее были уточне ны для отдельных классов 3-многогранников. Но вплоть до ра боты [3] (2002 г.) ни один из этих параметров не был улучшен без ухудшения других ее параметров. О. В. Бородин в [3] улучшил девять параметров теоремы Лебега без ухудшения остальных.

Теорема (Бородин, [3]). Каждый 3-многогранник содер жит грань одного из следующих типов:

(3, 6, ), (3, 8, 22), (3, 9, 15), (3, 10, 13), (3, 11, 12), (4, 4, ), (4, 5, 17), (4, 6, 11), (4, 7, 8), (5, 5, 8), (5, 6, 6 ), (3, 3, 3, ), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5 ), (3, 3, 3, 3, 5 ).

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

В [3] была поставлена задача: найти уточнение теоремы Ле бега, не допускающее дальнейших усилений. Заметим, что ре шение этой задачи требует уточнения небольшого числа пара метров. В диссертации сделан один шаг в этом направлении, а именно член (4, 5, 17) заменяется на (4, 5, 16).

Во второй главе представлены результаты о 2-дистанцион ной раскраске разреженных плоских графов.

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

Существует гипотеза Г. Вегнера (1977 г.) [11] о том, что 2 (G) 3 (G)+1 для любого плоского графа G с максималь ной степенью (G). Первый результат в этом направлении был получен Я. Ван-ден-Хойвелом и С. Мак Гиннессом [10], дока завшим что 2 (G) 2 + 25. В [2] О. В. Бородин, А. Н. Глебов, Х. Брусма и Я. Ван-ден-Хойвел доказали, что для произволь 9 (G)+1 при (G) ных плоских графов 2 (G) 47, что улучшило оценку Г. Агнарсона и М. М. Холдорсона: 2 (G) 9 (G)+2 при (G) 749.

Для любого графа G с максимальной степенью очевидной нижней оценкой для 2 является +1, так как +1 есть необхо димое число цветов для 2-дистанционной раскраски -звезды, содержащейся в любом графе. В частности, эта оценка достига ется на всех деревьях, но не достигается, например, на циклах C3k+1. Обхватом g(G) графа G называется наименьшая длина цикла в G. Вопрос о том для сколь малых g можно гарантиро вать равенство 2 (G) = + 1 путем наложения ограничения только на был полностью решен в [12, 13].

Результаты, включенные в диссертацию из работ [12, 13], получены диссертантом и представлены в виде теоремы 2.1.

Теорема 2.1. Пусть G планарный граф, тогда 2 (G) = + 1 в каждом из следующих случаев:

(i) = 4 и g 15;

(ii) = 5 и g 13;

(iii) = 6 и g 12;

(iv) 7 и g 11;

(v) 9 и g = 10;

(vi) 16 и g = 9;

(vii) 30 и g = 7.

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

В [13] было показано существование плоских графов с g 6, для которых 2 + 1 при произвольно большом. Таким образом, определенное нами условие на обхват, g 7, является неулучшаемым для 2-дистанционной ( + 1)-раскрашивамости плоского графа. При этом доказательство утверждения (vii) в теореме 2.1 было технически наиболее сложным.

Ввиду сказанного в предыдущем абзаце для обеспечения 2-дистанционной ( + 1)-раскрашиваемости плоского графа G обхвата 6 потребовалось ввести дополнительное структурное тре бование: хотя бы один из концов каждого ребра графа G явля ется вершиной степени 2. В [14] было доказано, что если G плоский граф обхвата 6, в котором (G) 179, а каждое ребро инцидентно 2-вершине, то 2 (G) = (G)+1. В диссертации этот результат был усилен следующим образом.

Теорема 2.2. Если G плоский граф обхвата 6, в котором (G) 31, а каждое ребро инцидентно 2-вершине, то 2 (G) = (G) + 1.

Третья глава содержит результаты о (p, q)- и предписан ной (p, q)-раскрасках плоских графов достаточно большого об хвата.

Раскраска вершин графа G называется (p, q)-раскраской, ес ли вершины графа G, расстояние между которыми равно 1, по лучают цвета, отличающиеся друг от друга не менее чем на p, а на расстоянии 2 не менее чем на q. Если при этом для каждой вершины задан список допустимых цветов, то говорят о пред писанной (p, q)-раскраске. Наименьшее число цветов в (p, q)-рас краске графа G называется (p, q)-хроматическим числом графа G и обозначается через p,q (G). Аналогично определяется пред писанное (p, q)-хроматическое число l (G). p,q Понятно, что ранее рассмотренная 2-дистанционная раскрас ка является в точности (1, 1)-раскраской.

Для (p, p)-хроматического числа произвольного графа G име ем очевидную нижнюю оценку: p,p (G) p + 1 (из тех же соображений, что и для (1, 1)-раскраски). Заметим, что всегда p,p(G) p · 1,1 p + 1, так как минимальную (1,1)-раскраску цветами 0, 1,..., 1,1 1 можно преобразовать, умножением всех ее цветов на p, в (p, p)-раскраску цветами 0, p,..., (1,1 1)p. По этому ввиду теоремы 2.1 можно утверждать, что если G плос кий граф обхвата не менее 7, то p,p (G) = p + 1 при 30.

Для плоского графа О. В. Бородин, А. Н. Глебов, Х. Брусма и Я. Ван-ден-Хойвел [2] доказали, что p,q (G) 10p + c, где c величина, не зависящая от p, а для разреженного плоского графа при p q 1 справедлива доказываемая в диссертации Теорема 3.1. Пусть G планарный граф обхвата не менее 31. Тогда p,q (G) 2p + ((G) 1)(2q 1) при (G) 5.

Ясно, что при p q данная оценка лучше той, что приве дена выше для p = q. Что касается нижней оценки (p, q)-хрома тического числа, то доказано Предложение 3.2. Существуют такие плоские графы G произвольного обхвата со сколь угодно большим, что p,q (G) 2p + 1 + ( 2)q.

Таким образом, при p q главный член, равный 2p, в тео реме 3.1 не допускает улучшения.

Очевидно, что l (G) p,q (G) для любого графа G. При p,q l (G) может сколь угодно сильно отличаться q = 0 величина p,q от p,q (G).

Предложение 3.3. Для любого n 1 существует граф G такой, что p,0 (G) = p + 1, а l (G) n(2p 1).

p, Что касается предписанных (p, q)-раскрасок при q 1, то во прос о существовании графа G, для которого l (G) = p,q (G), p,q остается открытым. Для произвольных плоских графов в [2] доказана та же оценка: l (G) 10p + c, что и для p,q (G).

p,q Для предписанного (p, q)-хроматического числа в диссертации доказывается та же верхняя оценка, что и для обычной (p, q) раскраски, а именно Теорема 3.4. Пусть G планарный граф обхвата не менее 2p 5( ((G)2)(2q1) + 4) + 1. Тогда l (G) 2p + ((G) 1)(2q 1) p,q при (G) 4.

Отметим, что ограничение на обхват в теореме 3.4, в отличие от теоремы 3.1, является растущей функцией от p при фикси рованных q и (G). Следующий факт частично объясняет это обстоятельство.

Предложение 3.5. В задаче предписанной (p, q)-раскраски в p 2p+((G)1)(2q1) цветов k-цепь, где k 2 ((G)1)(2q1) +1, не является сводимой конфигурацией при (G) 2.

Тем самым достаточные условия для предписанной (p, q) раскрашиваемости оказываются, вообще говоря, более жестки ми, чем для обычной (p, q)-раскраски в одно и то же число цве тов.

Автор выражает искреннюю благодарность своему научному руководителю О. В. Бородину за постановку задач, постоянное внимание и всестороннюю поддержку, А. Н. Глебову за внима тельное прочтение рукописей большинства статей и полезные обсуждения и А. О. Ивановой за помощь в подготовке диссерта ции.

Список литературы [1] Бородин О. В. Строение и раскраска плоских графов: Дис.

... док.физ.-мат.наук: 01.01.09. Новосибирск. 1994. 239 c.

[2] Бородин О. В., Брусма Х., Глебов А. Н., Ван-ден-Хойвел Я.

Строение плоских триангуляций в терминах пучков и звезд // Дискрет. анализ и исслед. операций. Сер. 1. 2001.

Т. 8, № 2. С. 15–39.

[3] Бородин О. В. Усиление теоремы Лебега о строении млад ших граней в выпуклых многогранниках // Дискрет. анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 3. С. 29–39.

[4] Borodin O. V. Cyclic degree and cyclic coloring of 3-polytopes // J. Graph Theory. 1996. Vol. 23, № 3. P. 225–231.

[5] Borodin O. V. Triangulated 3-polytopes without faces of low weight // Discrete Math. 1998. Vol. 186. P. 281–286.

[6] Grnbaum B. Acyclic coloring of planar graphs // Israel J.

u Math. 1973. Vol. 14, № 3. P. 390–408.

[7] Jensen T.R., Toft B. Graph coloring problems. New York: John Wiley & Sons, Jnc., 1995.

[8] Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat. Casopis. 1955. Vol. 5. P. 101–113.

[9] Lebesque H. Quelques consequences simples de la formule d’Euler // J. Math. Pures Appl. 1940. Vol. 9. P. 27–43.

[10] Van den Heuvel J., McGuinness S. Coloring the square of planar graph // Unpublished manuscript. 1999.

[11] Wegner G. Graphs with given diameter and a coloring problem // Technical Report. University of Dortmund. 1977.

Работы автора по теме диссертации [12] Бородин О. В., Иванова А. О., Неустроева Т. К. 2-дистанци онная раскраска разреженных плоских графов // Сибирские Электронные Математические Известия. 2004. Т. 1. C. 76– 90.

[13] Бородин О. В., Глебов А. Н., Иванова А. О., Неустрое ва T. К., Tашкинов В. А. Достаточные условия 2-дис танционной ( + 1)-раскрашиваемости плоских графов // Сибирские Электронные Математические Известия. 2004.

T. 1. С. 129–141.

[14] Бородин О. В., Иванова А. О., Неустроева Т. К. Достаточ ные условия 2-дистанционной ( + 1)-раскрашиваемости плоских графов с обхватом 6 // Дискретный анализ и ис следованте операций. Сер. 1. 2005. Т. 12, № 3. С. 32–47.

[15] Бородин О. В., Иванова А. О., Неустроева Т. К. 2-дистан ционная и ориентированная раскраски разреженных плос ких графов // X Лаврентьевские чтения, посвященные 50-летию Якутского государственного университета им.

М.К.Аммосова: Научная конференция. Сборник статей.

Том. I: Секция "Математика, механика и физика "Техни ческие науки и науки о Земле". Якутск: Изд-во ЯГУ. 2006.

С. 27–37.

[16] Бородин О. В., Иванова А. О., Неустроева Т. К. О строе нии младших граней в выпуклых многогранниках // Мат.

заметки ЯГУ. 2006. T. 13. Вып. 1. С. 29–44.

[17] Бородин О. В., Иванова А. О., Неустроева Т. К. (p, q)-рас краска разреженных плоских графов // Мат. заметки ЯГУ.

2006. T. 13. Вып. 2. С. 13–19.

[18] Бородин О. В., Иванова А. О., Неустроева Т. К. Предписан ная (p, q)-раскраска разреженных плоских графов // Сибир ские Электронные Математические Известия. 2006. Т. 3.

C. 355–361.

[19] Бородин О. В., Иванова А. О., Неустроева Т. К. Достаточ ные условия 2-дистанционной ( + 1)-раскрашиваемости плоских графов с обхватом 6 // Сибирские Электронные Математические Известия. 2006. Т. 3. C. 441–450.

[20] Иванова А. О., Неустроева Т. К. О (p, q)-раскраске раз реженных плоских графов // IV Всероссийская школа семинар студентов, аспирантов, молодых ученых и специа листов "Математическое моделирование развития северных территорий РФ": Тез. докл. Якутск: Филиал изд-ва ЯГУ.

2006. С. 38–40.

Неустроева Татьяна Кимовна Строение младших граней и (p, q)-раскраски плоских графов Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Подписано в печать 5.03.07. Формат 60х84 1/16.

Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз.

Заказ N 44.

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



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.