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

• Автор: Неустроева, Татьяна Кимовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Новосибирск
• Количество страниц: 78 с.

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. Доказательство результатов о предписанной (р, д)-раскраске
Список литературы
1. Общая характеристика работы
Задачи раскраски графов интересуют многих специалистов не только по теории графов и дискретной математике, но и физиков, программистов, экономистов и других. Этот интерес вызван тем, что задачи о раскрасках графов имеют разнообразные приложения, в частности, в задаче назначения радиочастот в сетях мобильного телефонирования, в задаче оптимальной организации структуры баз данных, распределения ресурсов, в задачах, возникающих при планировании производства, составлении графиков осмотра и хранения товаров и т. д.
Наиболее широко известной из задач раскраски графов является знаменитая проблема четырех красок (1852 г.): требуется доказать возможность раскрасить плоскую карту четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Доказательство было дано более чем через 120 лет К. Аппелем и В. Хакеном [12, 13, 14]. Решение состояло в построении так называемой “неизбежной системы сводимых конфигураций”, а именно в нахождении такой системы структурных фрагментов, что хотя бы один из них содержится в каждом графе рассматриваемого класса, причем каждая из этих конфигураций является сводимой, т. е. должна отсутствовать в минимальном контрпримере к данной задаче о раскраске. Метод сводимых конфигураций применяется для решения подавляющего большинства задач раскраски плоских графов. Наиболее полную информацию о результатах в области раскраски графов, полученных до середины 90-х годов прошлого столетия, можно найти в книге В. Тофта и Т. Р. Йенсена [25].
Отметим, что первоначально большинство фактов о строении плоских графов, установленных при решении задач о раскрасках, использовались только в рамках рассматриваемой задачи, т. е. интерес к локальным свойствам графов возникал только применительно к задачам раскраски. Один из первых шагов в изучении структуры плоских графов был сделан А. Лебегом в 1940 г. Созданная А. Лебегом [30] теория эйлеровых вкладов, основанная на преобразовании известной формулы Эйлера для многогранников, в дальнейшем получила широкое применение и развитие в работах
А. Коцига [27]-[29], Б. Грюнбаума [21]-[23] и других. Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [7, 9, 10, 8,19]. Перечисленные, а также и многие другие работы но раскраскам плоских графов позволили теоремам о строении плоских графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов. Введение в эту теорию представлено в докторской диссертации
О.В. Бородина [7].
Заметим, что структурные теоремы, полученные в перечисленных выше работах, касаются плоских графов с минимальной степенью 5 ^ 3. Что же касается плоских графов с 5 = 2, то, хотя об их строении известно довольно много, стройной классификации этих графов в настоящее время пока нет. Интерес к изучению строения плоских графов с 5 = 2 вызван возможностью применения структурных свойств этих графов к некоторым видам раскраски графов, в частности, реберной, тотальной, 2-дистанционной, (р, д)-раскраске, ориентированной, предписанной и других.
В диссертации рассматриваются (р, д)-раскраска и частный случай этого вида раскраски, 2-дистанционная, разреженных плоских графов (имеющих заданный обхват), при изучении которых мы сталкиваемся с графами, имеющими <5 = 2.
Задача (р, Цель настоящей работы состоит в получении новых результатов о строении младших граней в 3-многогранниках и (р, д)-раскраске (в том числе и предписанной) разреженных плоских графов, причем в диссертации большое внимание уделяется наиболее важному частному случаю этой раскраски — 2-дистанционной.
Результаты работы носят теоретический характер. Результаты о (р, ^-раскрасках плоских графов в перспективе могут быть использованы при решении проблемы распределения радиочастот в сетях мобильной связи.
Доказательство. Пусть д(у) ^ А - к(у) + ^(и) и <1(у) ^ Д - 1. По лемме 3 имеем с£(ш) = А. Удалим перечеркнутое ребро и обесцветим вершину V, смежные с и вершины, кроме лежащих на жестких 1-цепях, все 2-вершины пучка В, центральные вершины особых 3-цепей и младшие вершины, находящиеся на расстоянии 2 от у (см. рис. 2).
Пусть £ — толщина пучка В. Покрасим V в один из цветов, встречающихся на ы или на оставшихся окрашенными вершинах, смежных с ш. Таких цветов имеется А - £ + 1, а на выбор цвета для V имеется не более б{у) - £ + кі(у) - УД и) ^ А - £ ограничений (поскольку неособые жесткие 1-цепи дают по 2 ограничения, тогда как остальные неособые цепи - одно ограничение, а две цепи каждой особой грани вместе дают два ограничения), т.е. V всегда можно покрасить в цвет вершины ш или ее соседей. Затем красим смежные с гг вершины из В (на последнюю имеется А ограничений, так как цвет вершины у при пей встречается дважды); затем красим смежные с у вершины (что возможно, так как £ ^ 6 и (1(у) ^ А -1; последней красится вершина у, и при этом, если нужно, делается подкрутка) и, наконец, центральные вершины особых 3-цепей и младшие вершины, находящиеся на расстоянии 2 от V. □
Лемма 5. Если вершина у является концом пучка толщины не менее 6, то у инцидентна жесткой неособой 1-цепи либо непучковой 2-цепи.
ДОКАЗАТЕЛЬСТВО. Удалим ребро ии одного из пучков В при и. Обесцветим и, вес смежные с ней вершины, кроме лежащих на особых 1-цепях, младшие концы 1-цепей и центральные вершины 3-цепей. Пусть конец пучка В, отличный от у, окрашен в цвет 1. Если вершину у можно покрасить в цвет 1, то раскраску можно продолжить следующим образом: раскрасим сначала непучковые вершимы, смежные с: и. а потом 2-вершины в пучках. Вершину и красим последней из пучковых; если нужно, применяем подкрутку. Последними красим младшие вершины и центральные вершины