Строение младших граней и (P, Q)-раскраски плоских графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Неустроева, Татьяна Кимовна

• Неустроева, Татьяна Кимовна
• кандидат физико-математических наук
• 2007

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

Введение.

1. Общая характеристика работы.

2. Основные определения и обозначения.

3. Краткий обзор результатов диссертации

1. Строение младших граней эйлеровых многогранников

1.1. Формулировка основного результата главы

1.2. Доказательство теоремы 1.

2. 2-дистанционная раскраска плоских графов

2.1. Обзор результатов главы

2.2. Доказательство теоремы 2.

2.2.1. Случай д ^

2.2.2. Случай д =

2.3. Доказательство теоремы 2.

2.3.1. Структурные свойства минимального контрпримера

2.3.2. Окончательное распределение зарядов и его следствия

3. Задача (р, д)-раскраски плоских графов.

3.1. Обзор результатов главы

3.2. Доказательство результатов о (р, <?)-раскраске

3.3. Доказательство результатов о предписанной (р, г/)-раскраскс

Введение диссертации (часть автореферата) на тему «Строение младших граней и (P, Q)-раскраски плоских графов»

1. Общая характеристика работы

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

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

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

А. Коцига [27]-[29], Б. Грюнбаума [21]-[23] и других. Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [7, 9, 10, 8,19]. Перечисленные, а также и многие другие работы по раскраскам плоских графов позволили теоремам о строении плоских графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов. Введение в эту теорию представлено в докторской диссертации О. В. Бородина [7].

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

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

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

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

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

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

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

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

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

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

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

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

По теме диссертации опубликованы 7 журнальных статей [37, 38, 39, 41, 42, 43, 44], одна статья в трудах конференции [40] и заметка в сборнике докладов [45].

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

Список литературы диссертационного исследования кандидат физико-математических наук Неустроева, Татьяна Кимовна, 2007 год

1. Августинович С. В., Бородин O.B. Окрестности ребер в нормальных картах // Дискретный анализ и исследование операций. 1995. Т. 2, № 3. С. 3-9.

2. Бородин О. В. Решение задач Коцига и Грюнбаума об отделимости цикла в плоском графе // Мат. заметки. 1989. Т. 46, выи. 5. С. 9-12.

3. Бородин О. В. Оценки для числа легких ребер в плоских графах. Новосибирск, 1989. 12 С. (Препринт / АН СССР Сиб. отделение Ип-т математики; Л'1-' 6.)

4. Бородин О. В. Совместное обобщение теорем Лебега и Кои,ига о комбинаторике плоских карт // Дискретная математика. 1991. Т. 3, вып. 4. С. 24-27.

5. Бородин О. В. Минимальный вес грани в плоских триангуляциях без 4-вершин II Мат. заметки. 1992. Т. 51, вып. 1. С. 16-19.

6. Бородин О. В. Структурная теорема о плоских графах и се приложение, к раскраске // Дискретная математика. 1992. Т. 46, вып. 1. С. 60-65.

7. Бородин О. В. Строение и раскраска плоских графов: Дис. . док.физ-мат.наук: 01.01.09. Новосибирск. 1994. 239 с.

8. Бородин О. В. Раскраски и топологические представления грифов , Дискретный анализ и исследование операций. 1996. Т. 3, № 4. С. 3-27.

9. Бородин О. В., Брусма X., Глебов А. Н., Ван ден Хойвел Я. Строение плоских триангуляций в терминах пучков и звезд // Дискретный анализ и исследование операций. Сер. 1. 2001. Т. 8, № 2. С. 15-39.

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

11. Agnarsson G., Halldorsson М. М. Coloring powers of planar graphs // Unpublished manuscript. 2000.

12. Appel K., Haken W. The existence of unavoidable sets of geographically good configurations // Illinois J. Math. 1976. V. 20. P. 218-297.

13. Appel K., Haken W. The solution of the four-color-map problem i/ Scientific American. 1977. Vol.237, № 4. P. 108-121.

14. Appel K., Haken W. The four color proof suffices 11 Math. Intelligencer. 1986. Vol.8, № 1. P. 10-20.

15. Borodin O.V. An extention of Kotzig's theorem on the minimum weight of edges in Z-polytopes // Math. Slovaca. 1992. Vol.42, № 4. P. 385-389.

16. Borodin O.V. Joint extension of two theorems of Kotzig on Z-polytopes // Combinatorica. 1993. Vol. 13, № 1. P. 121-125.

17. Borodin 0. V. Cyclic degree and cyclic coloring of 3-polytopes //J. Graph Theory. 1996. Vol. 23, № 3. P. 225-231.

18. Borodin O. V. More about the weight of edges in planar graphs // Tatra Mountains Math. Publ. 1996. V. 9. P. 11-14.

19. Borodin O.V. Triangulated Z-polytopes without faces of low weight, // Discrete Math. 1998. Vol. 186, N 1-3. P. 281-286.

20. Borodin O.V., Woodall D.R. Cyclic degree of Z-polytopes // Graphs and Combinatorics. 1999. Vol. 15, № 3. P. 267-277.

21. Griinbaum B. Acyclic coloring of planar graphs // Israel J. Math. 1973. Vol.14, № 3. P. 390-408.

22. Griinbaum B. New views on some old questions of combinatorial geometry / /' Proc. Intern. Colloq. Rome, 1973 / Accademia Nacionale dei Lincei. 1976. P. 451-468.

23. Griinbaum B., Shephard G.C. Analogues for tillings of Kotzig's theorem on minimal weight of edges // Annals of Discrete Math. 1981. Vol. 12. P. 129-140.

24. Horna'k M., Jendrol' S. Unavoidable sets of face types for planar maps // Discus. Math. Graph Theory. 1996. Vol. 16, № 2. P. 123-142.

25. Jensen T.R., Toft В. Graph coloring problems. New York: .John Wiley к Sons, Jnc., 1995.

26. Jucovic E. Strengthening of a theorem about 3-polytopes // Geometriae Dedicata. 1974. Vol.3. P. 233-237.

27. Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat. Casopis. 1955. Vol.5. P. 101-113.

28. Kotzig A. From the theory of Euler's polyhedrons // Mat. Casopis. 1963. Vol.3. P. 20-34.

29. Kotzig A. Extremal polyhedral graphs // Proc. Second Intern. Conf. on Combin. New York: New York Acad, of sei., 1979. P. 569-570.

30. Lebesque H. Quelques consequences simples de la formale, d'Etiler // .]. Math. Pures Appl. 1940. Vol.9. P. 27-43.

31. Ore O., Plummer M.D. Cyclic coloration of plane graphs // Recent Progress in Combinatorics. New York: Acad. Press, 1969. P. 287-293.

32. Plummer M.D., Toft B. Cyclic coloration of 3-polytopes // J. Graph Theory. 1987. Vol. 11, N 4. P. 507-515.

33. Shannon С. E. A theorem on coloring the lines of a network //' J. Math, and Pliys. 1949.V. 28. P. 148-151.

34. Steinitz E. Polyheder und Raumeinteilungen // Enzykl. math. Wiss. 1922. Vol. ЗАВ (Geometrie), N 12. P. 1-139.

35. Van den Heuvel J., McGuinness S. Coloring the square, of planar graph '/ Unpublished manuscript. 1999.

36. Wegner G. Graphs with given diameter and a coloring problem // Technical Report. University of Dortmund. 1977.Работы автора по теме диссертации

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

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

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

40. Бородин О. В., Иванова А. О., Неустроева Т. К. О строении младших граней в выпуклых многогранниках // Мат. заметки ЯГУ. 2006. Т. 13, вып. 1. С. 29 -14.

41. Бородин О.В., Иванова А.О., Неустроева Т.К. (р, д)-раскраска разраженных плоских графов // Мат. заметки ЯГУ. 2006. Т. 13, вып. 2. С. 13-19.

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

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