WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ

МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В. А. СТЕКЛОВА РАН

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

Гравин Николай Вадимович

Некоторые аспекты правильных раскрасок

графов

01.01.09 дискретная математика и математическая кибернетика

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

Научный руководитель:

доцент, к.ф.-м.н. Д. В. Карпов Санкт-Петербург 2010 Оглавление 1 Введение 1.1 Определения.......................... 1.1.1 Базовые понятия.................... 1.1.2 Понятия связанные с раскрасками.......... 2 Гиперграфы и Динамичиские раскраски 2.1 Верхние оценки на хроматическое число для гипер-графов 2.2 Верхние оценки на динамическое хроматическое число.. 3 Теорема Брукса и Динамические Раскраски 3.1 (c, p)-невырожденность.................... 3.2 Доказательство Основного Результата............ 3.2.1 Часть первая....................... 3.2.2 Часть вторая....................... 4 Алгоритмы для Раскрасок Графов 4.1 Обозначения.......................... 4.1.1 Терминология...................... 4.1.2 Основной результат.................. 4.2 Задача Списковой d-раскраски................ 4.2.1 Алгоритм........................ 4.2.2 Реализация процедур................. 4.2.3 Доказательство корректности алгоритма...... 4.2.4 Анализ сложности алгоритма............. 4.3 Конструктивное доказателсьво теоремы Брукса...... Глава Введение Graph theory is very important for mathematics and informatics Теория графов является одним из важнейших и интереснейших разделов математики. Помимо многочисленных приложений в различные областях математики таких, как теория вероятностей, комбинаторика, алгебра и топология, она является краеугольным камнем в современной информатике, как теоретической, так и прикладной. В любом учебнике по алгоритмам едва ли не треть всего материала будет посвящена алгоритмам на графах. Терминология теоретической информатики же не мыслима без использования понятий теории графов как то дерево, вершина, ребро, путь, цикл и более сложных, таких как экспандер.

Colorings are one of the most dicult though very popular and long studied topic History and overview of main results in coloring Правильные раскраски графов на сегодняшний день вероятно являются одной из самых полпулярных тем в теории графов. Хотя уже проблема раскрашиваемости графа в 3 цвета является NP-полной задачей, существует несколько положительных результатов описывающих случаи, где число допустимых цветов близко к максимальной степени графа. Пожалуй самой известной среди них является теорема Брукса [14], утверждающая, что связный граф, не являющийся нечетным циклом или кликой, можно всегда раскрасить в цветов. Однако, вопрос становится гораздо труднее уже для раскраски в 1 цвет. В 1977 году Бородин и Косточка [13] выдвинули гипотезу, что для 9 графы без клик размера могут быть раскрашены в (1) цвет. Гипотеза до сих пор остается открытой, однако в случае 1014 она была положительно решена Риидом [24] при помощью вероятностного метода.

Другое обобщение теоремы Брукса связанное со списковыми раскрасками было независимо предложено Визингом [28] и Ердешем с соавторами [16]. Недавно это направление даже приобрело большую популярность, чем правильные раскраски, см. например [18, 27, 22, 20] и многие другие источники, один из самых последних результатов [19]. В 1994 на конференции по теории графов в Обервольхе Томассеном было отмечено, что помимо теормы Брукса можно также обобщить для списковых раскрасок классическую теорему Галлаи [17], в которой описываются все подграфы k-раскрасочно-критических графов индуцированных на вершинах степени k 1. Удивительно, но как отметил Косточка в [21], обобщение теоремы Галлаи может быть легко выведено из результатов Бородина [11, 12] и Ердеша, Рубина и Тейлора [16]. Более подробно, Ердеш характеризовал d-списочно раскрашиваемые графы, как графы содержащие блок, который не является ни кликой, ни нечетным циклом. В этой характеризации никак не упоминается случай раскраски не d-списочно раскрашиваемоего графа, если помимо самого графа задан набор списков (в этом случае ответ может быть отрицательным).

Последнее было сделано Бородиным в малоизвестной работе [11].

My contribution organization of the dissertation 1.1 Определения В диссертации, если не оговорено противное, мы будем рассматривать неориентированные графы без петель и кратных ребер, множество вершин графа G мы всегда будем обозначать через V (G), а множество ребер через E(G).

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

1.1.1 Базовые понятия Определение. Пусть S V (G), индуцированным подграфом G(S) графа G называется граф на множеством вершин S содержащий те и только те ребра G, оба конца которых лежат в S.

будем обозначать граф, получающийся при удалении всех вершин множества W и всех выходящих из них ребер. Для F E(G) через G F мы будем обозначать граф, который получается при удалении из G всех ребер множества F (то есть, G F = (V (G), E(G) \ F )).



Через degG (u) или deg(u) мы будем обозначать степень вершины u в G, т.е. число инцендентных с u ребер. Следуя книге [1] через (G) и (G) мы будем обозначать минимальную и максимальную степени графа G.

Окрестностью вершины v V (G) в графе G называется множество NG (v) = {u V (G) : uv E(G)}. Вершины из NG (v) называются соседями v.

Определение. Пусть S V (G), обозначим через Nv (S) окрестность вершины v в графе G(S {v}). Мы будем писать для краткости Nv в случае S = V (G).

Определение. Обозначим через |G| размер графа G, определяемый как количество ребер плюс количество вершин в G.

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

Граф называется двусвязным, если при удалении любой вершины, он остается связным (мы предполагаем здесь, что пустой граф является связным). Блоком связного графа G назывется максимальный по включению двусвязный подграф G.

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

Правильной раскраской графа G называется отображение c : V (G) N такое, что c(v) = c(u), если uv E(G). Раскраска c назывется kраскраской, если всего было использовано не более k цветов. Пусть c – правильная раскраска G в k цветов, а множество V V (G), тогда через c(V ) мы будем обозначать ограничение отображения c на множество V, т.е. правильную раскраску графа G(V ) в k цветов.

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

Более формально, списковым набором является функция L ставящая в соответсвие каждой вершине v V (G) некоторое множество L(v) натуральных чисел, которые зовутся допустимыми цветами вершины v. Тогда L-раскраской G будет называться такая правильная раскраска c графа G, что каждой вершине v соответсвует цвет c(v) L(v).

В случае, если |L(v)| k для любой вершины v V (G), мы будем говорить, что L является k-набором, если же |L(v)| deg(v) для каждой вершины v V (G), мы будем говорить, что L является d-набором.

Частичной L-раскраской подмножества вершин S графа G называется L-раскраска индуцированного подграфа G(S). L-раскраска C графа G называется расширением частичной раскраски C на множестве вершин S, если C(v) = C (v) для всех v S.

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

Глава Гиперграфы и Динамичиские раскраски Определение 2.1. Назовем k-редукцией графа G максимальный по включению подграф Rk (G) графа G, в котором степень любой вершины по крайней мере k. Если такого подграфа нет, то определим пустой граф как k-редукцию G. В последнем случае G будет назыаться k-редуцируемым графом.

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

2.1 Верхние оценки на хроматическое число для гипер-графов Теорема 2.1. Пусть H = (V, E) является -гиперграфом с максимальной степенью вершины. Тогда H можно раскрасить в + 1 цветов.

Доказательство. Обозначим + 1 через k.

Определение 2.2. Назовем гафом образом или просто образом некоторого гиперграфа H = (V, E) любой граф с мульти-ребрами G = (V, E), для которго V = V и между ребрами E и E есть биективное соответствие такое, что каждое гипер-ребро F E включает соответсвующее ребро из E.

Чтобы доказать теоерему, достаточно построить раскрашиваемый в k цветов образ гипер-графа H. Предположим от противного, что такого образа не существует, рассмотрим тогда образ G1 графа H с наименьшим возможным |Rk (G1 )|. Так как каждый k-редуцируемый граф k-раскрашиваем, Rk (G1 ) не пусто. Зафиксируем граф H1 = Rk (G1 ) и обозначим множнство его вершин через S1.

Для доказательства теоремы нам понадобится конструкция. В ней на шаге i мы строим следующее:

1. последовательность множеств S1 S2... Si V ;

2. последовательность графов Hj, где j [1, i] и V (Hj ) = Sj ;

3. существует по крайней мере один образ Gi графа H с Rk (Gi ) = H и Hj = Gi (Sj ) для всех j [1, i]; обозначим множество всех таких 4. для любого j [1, i] не существует образа G гипер графа H с Rk (G) = H1 и E(G(Sj )) E(Hj ), т.е. Hj является минимальным по включению индуцированным подграфом на множестве Sj взятом среди всех образов G гипер графа H с условием Rk (G) = H1 ;

Легко видеть, что S1, H1 и G1 удовлетворяют всем условиям для i = 1.

Так как |Si | ограничено сверху, для завершения доказательства нам достаточно продолжить конструкцию на следующий i+1 шаг для любого 1. Заметим, что обязательно найдется ребро e E(Hi ) и соответсвующее ему гипер-ребро F E с вершиной v F, v Si.

Последнее выполнено, так как в противном случае по условию 5 для графа H размера. Следовательно, по принципу дирихле найдется вершина H степени больше чем, что противоречит условию 2. Пусть e = (u, w). Для каждого графа G Gi попытаемся заменить e на (u, v). Получившийся граф Ge будет образом H, E(Ge (Sj )) E(Hj ) для всех j [1, i] и кроме того для некоторого j включение будет строгим. Таким образом по условию 4 нашей кострукции получаем, что Rk (Ge ) = H1. Если v Rk (Ge ), тогда Rk (Ge ) Rk (G). Но значение |Rk (G)| было минимально возможным и значит мы приходим к противоречию. Следовательно v Rk (Ge ). Для каждого графа G Gi положим SG = V (Rk (Ge )) и HG = G(Si S). Таким образом получаем v SG и значит v V (HG ).

3. Возьмем G из Gi с минимально возможным |HG | и положим Gi+1 = G. Возьмем в качестве Si+1 множество SG Si, а в качестве Hi+ возьмем G(Si+1 ). Так как v Si+1 и v Si, имеем Si Si+1 V.

Отсюда получаем, что условие 1 конструкции выпрлненно для i + 1;

свойства 2 и 3 выполняются по определению Hi+1 и Si+1 ; условие 4 выполнено в силу выбора HG = Hi+1 ; каждая вершина из SG в для i + 1, что завершает доказательство теоремы.

2.2 Верхние оценки на динамическое хроматическое число Определение 2.3. Динамической раскраской графа G в k цветов называется отображение c : V (G) {1, 2,..., k} такое, что для любой вершины v графа G в множестве Nv (G) найдется по крайней мере два различных цвета.

Замечание. Динамическая раскраска не обязана быть правильной раскраской.

Теорема 2.2. Дан граф G с максимальной степенью и минимальной степенью. Тогда G допускает динамическую раскраску в + цветов.

Доказательство. Рассмотрим следующий гипер-граф H.

• Множество вершин H совпадает с V (G).

• Множество гипер-ребер H состоит из множеств Nv для всех v Теорема эквивалентна тому факту, что H допускает k-раскраску.

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

Глава Теорема Брукса и Динамические Раскраски Настоящая глава посвящена обобщению широко известной теоремы Брукса [2], которая говорит нам, что (G) (G) для любого графа G без полных подграфов на d + 1 вершине с (G) > 2.

Обобщение заключается в том, что мы дополнительно накладываем требование (c, p)-невырожденности на раскраску графа.

3.1 (c, p)-невырожденность Ранее предпринимались попытки получить похожие на теорему Брукса утверждения с дополнительным условием c-невырожденности говорящем, что среди соседей любой вершины графа степени хотя бы c должны найтись c вершин различных цветов. Так, в работах [3, 4] были найдены оценки на количество цветов, в которое можно правильным 2-невырожденным образом покрасить граф. Случай c = 2 особенно интересен, в виду тесной связи динамических раскраскок и правильных раскраско гиперграфов. Стоит отметить однако, что полученные в этих работах результаты не являются обобщениями теоремы Брукса, т.к. количество цветов, в которое красится граф, больше.

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

Приведем соображение, заставляющее задуматься о необходимости изменения постановки задачи. Действительно, рассмотрим двудольный граф, у которого все вершины первой доли имеют степень c, а второй доли. Условие невырожденности для любой вершины v из первой доли говорит нам, что соседи v покрашены в различные цвета, что эквивалентно наличию клики при правильной раскраске. Условие невырожденности можно тогда переформулировать в терминах нахождения правильной раскраски вершин второй доли, в которой мы построили клики на всевозможных окрестностях вершин первой доли. Необходимо отметить, что в новом графе вершины второй доли могут иметь степень порядка (c 1). Таким образом даже в этом частном случае при c > трудно надеятся на нахождение правильной невырожденной раскраски с количеством цветов близким к.

Ключевым соображением, позволившим сделать серьезные продвижения в направлении обобщения теоремы Брукса является то, что мы потребуем несколько иное условие невырожденности раскраски, которое назовем (c, p)-невырожденностью. А именно, чтобы раскраска была невырожденной в обычном смысле не для всех вершин, а для вершин достаточно большой степени.

Определение 3.1. Пусть даны натуральные числа c 2 и p c. Раскраска графа G называется (c, p)-невырожденной, если для любой вершины G степени хотя бы p среди ее соседей найдутся вершины хотя бы c различных цветов.

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

Теорема 3.1. Пусть дано число D 3 и граф G без клик на D + и (G) D. Тогда для любого c 2 существует правильная (c, p)невырожденная раскраска вершин графа G в D цветов, где В связи с нашим результатом нельзя не упомянуть работу [7], где авторами получены следующие довольно сильные результаты.

Определение 3.2. Раскраска графа называется -frugal, если никакая вершина графа не имеет в своей окрестности более чем соседей одного цвета.

Теорема 3.2. У Любого графа G с максимальной степенью 0 = e10 существует правильная log 8 -frugal раскраска в ( + 1) цвет.

Из этой теоремы очевидным образом можно получить:

Следствие. У Любого графа G с максимальной степенью 0 = e10 существует правильная (, 0 )-невырожденная раскраска в ( + 1) цвет.

Отсюда можно получить оценку невырожденности раскраски асимптотически гораздо лучшую, чем наша, используя при этом всего один лишний цвет. Однако между правильной раскраской в цветов и + цвет существует большая разница. Можно с легкостью рекурсивно покрасить граф в (G) + 1 цвет, однако аналогичное утверждение для (G) цветов представляется совсем не очевидным. Также необходимо отметить, что это следствие как и все результаты в работе [7] получены только для очень больших графов. По сравнению с числами 0 = e10, оценка p = (c3 + 8c2 + 19c + 6)(c + 1) представляется значительно меньшей. Она дает нам нетривиальный результат уже при c = 2 и p = 252, то есть уже для графов с 252.

Существует интересное соображение касающееся -frugal и (c, p)невырожденных раскрасок. Почему мы вообще изучаем правильные раскраски графов? Одним из объяснений может служить то, что раскраска графа G в c цветов есть в точности гомоморфизм G в граф Kc (определение и более полная информация касающаяся гомоморфизмов графов можно найти например в книге [8]). Далее можно сделать весьма естественный шаг и рассмотреть для каждой вершины графа множество ее соседей, или ее окрестность. Тогда условие (c, p)-невырожденности будет в точности означать, что для каждой вершины v c |NG (v)| p, размер образа ее окрестности при гомоморфизме будет не меньше c. То есть (c, p)-невырожденность накладывает ограничение снизу на размер образа отображения. А свойство того, что раскраска является -frugal, будет устанавливать верхнюю оценку на размер “ядра” отображения, где под размером ядра естественно понимать максимальный размер подмножества окрестности отображающегося в один цвет.

3.2 Доказательство Основного Результата Одним из основных этапов доказательства теоремы 1 является доказательство следующей теоремы 2, которая представляет отдельный интерес.

Теорема 3.3. Пусть дан граф G без клик размера D + 1 с максимальc+ i 2. Тогда в множестве раскрасок графа G в c + 1 цвет найдется такая раскраска, что:

G, соединяющих две вершины i-ого цвета, 2) для любого i раскраска не содержит клик размера i + 1 на вершинах i-ого цвета.

3) G(Vi ) i, где Vi это множество всех вершин i-ого цвета в G.

В частности, одним из прямых следствий этой теоремы является результат, близкий по смыслу к полученному л. Ловашем в работе [9], который говорит нам, что вершины любого графа G с G k можно разбить Следствие. Пусть дан граф G без клик размера D + 1 с максимальk i 2. Тогда вершины графа G можно разбить на k непересекающихся множеств V1, V2,...,Vk таких, что для любого i k в графе G(Vi ) не будет клик на i + 1 вершине и степени всех вершин в G(Vi ) будут не больше i.

Отметим, что (c, p)-невырожденность раскраски является весьма сильным условием. Даже в случае двудольного графа G возникают определенные турдности с раскраской графа в G цветов. Если зафиксировать количество цветов D, в которое мы красим граф, не ограничивая при этом максимальную степень графа, то утверждение теорема 3. становится неверной, причем уже для c = 2 и любого значения p.

Контрпример. В качестве первой доли G возьмем множество S1, состоящее из (p 1)D + 1 элемента, в качестве второй доли S2 возьмем множество всех p-элементных подмножеств множества S1 и соединим каждую такую выборку со всеми входящими в нее элементами из S (см. рис. 3.1). Попытаемся раскрасить получившийся двудольный граф в D цветов. Заметим, что по принципу Дирихле, в множестве S1 при любой раскраске графа G в D цветов найдется p вершин одного цвета, а значит соответствующая выборка во второй доли графа G будет смежна с вершинами только одного цвета.

Замечание. К сожалению, величина p(c) = (c3 + 8c2 + 19c + 6)(c + 1) для маленьких c дает достаточно большое значение. Вполне возможно, что даже с помощью нашего метода доказательства можно получить лучшую оценку. Однако, нашим методом получить асимптотику лучшую, чем c4 (1 + O(c1 )), не получится.

Утверждение 3.2.1. Не умаляя общности в теореме 3.1 можно считать, что степени всех вершин графа G не меньше p.

Рис. 3.2: Новый граф с большей минимальной степенью Доказательство. С графом G можно проделать следующую операцию:

взять две копии графа G и соединить в этих копиях все пары одинаковых вершин, степени которых меньше p (см. рис. 3.2).

Заметим, что, для нового графа выполнены все условия теоремы 3.1. Также заметим, что, если нам удастся покрасить правильным образом новый граф в D цветов с выполнением условия, что в окрестности каждой вершины степени хотя бы p будет c различных цветов, то мы автоматически раскрасим правильным образом в D цветов обе копии графа G с выполнением все того же условия. Проделав такую операцию несколько раз в итоге мы получим граф, в котором не будет вершин степени меньше p, ибо при каждой такой операции минимальная степень графа увеличивалась (если, конечно, в графе были вершины степени меньшей, чем p).

Доказательство теоремы 3.1 состоит из двух частей. В первой части мы сведем нашу теорему, попутно доказав теорему 3.3, к некоторой лемме (см. лемму 3.2.1). А во второй части мы собственно докажем эту лемму.

3.2.1 Часть первая.

Покрасим граф G произвольным образом в цвета 1, 2,..., c + 1. Поставим в соответствие каждому цвету i {1, 2,..., c + 1} число i, где сможем так выбрать i. Рассмотрим величину, которая вычисляется для данной раскраски графа G в цвета {1, 2,..., c + 1} следующим образом: := i, где fi – это количество ребер графа G, соединяюi= щих две вершины i-ого цвета. Рассмотрим такие раскраски графа G в c + 1 цвет, что значение для них минимально. Обозначим множество всех таких раскрасок через Gc. Очевидно, что Gc не пусто. Обозначим множество всех вершин i-ого цвета любой раскраски Gc через i. Тогда для любой раскраски графа G из множества Gc верны следующие утверждения.

Утверждение 3.2.2. Для любого цвета i {1, 2,..., c + 1} в раскраске и любой вершины v i, количество вершин цвета i смежных с v не превосходит i.

Доказательство. Предположим противное. Тогда, в силу условия c+ j = D найдется такой цвет j = i, что v смежна в графе G меj= нее чем с j вершинами цвета j. Перекрасив v в цвет j, мы получим меньшее значение. Противоречие.

Утверждение 3.2.3. Если какая-нибудь вершина v i смежна в раскраске ровно с i вершинами цвета i, то тогда для любого цвета j вершина v смежна ровно с j вершинами цвета j.

Доказательство. Предположим противное. Тогда, в силу условия c+ k = D, найдется такой цвет j = i, что v смежна в графе G меk= нее чем с j, а тогда, перекрасив v в цвет j, мы уменьшим значение.

Противоречие.

Утверждение 3.2.4. Если в раскраске вершина v i смежна хотя бы с одной вершиной своего цвета, то она смежна хотя бы с одной вершиной любого другого цвета.

Доказательство. В противном случае перекрасив v в цвет, с которым она не соединена, мы придем к противоречию с минимальностью ().

Докажем теперь, что в множестве раскрасок Gc есть раскраска, в которой ни для какого цвета i нет клик размера i + 1 в графе G на вершинах i-ого цвета. Назовем такие клики большими.

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

Для любой раскраски из Gc обозначим через () количество больших клик в. Обозначим через множество раскрасок из Gc с минимальным количеством больших клик. Пусть > 0 для раскрасок из Используя утверждение 3.2.3, получим:

Утверждение 3.2.5. Если взять вершину v из какой-нибудь большой клики в какой-то раскраске gc и перекрасить ее в любой другой цвет, то, во-первых, получится новая раскраска gc Gc, во-вторых, (gc ) (gc ).

Так как мы взяли минимальным, то количество больших клик останется неизменным. Значит, обязательно появится новая большая клика цвете, в который мы перекрасили v, кроме того получаем gc.

Утверждение 3.2.6. Пусть раскраска 1 и (1 ) > 0. Пусть C1 – большая клика i-ого цвета. Рассмотрим индуцированный подграф Gij графа G на всех вершинах i-ого и j-ого цвета. Тогда компонента связности в графе Gij содержащая C1 будет представлять собой полный граф размера i + j + 1.

Доказательство. Перекрасим произвольную вершину v1 C1 в цвет j. Согласно утверждению 3.2.5, мы получим новую раскраску 2.

При этом вершина v1 войдет в какую-то большую клику C2 j-ого цвета.

Перекрасим какую-нибудь отличную от v1 вершину v2 клики C2 в цвет i.

Опять, согласно утверждению 3.2.5, получим новую раскраску 3, в которой v2 обязательно должна войти в какую-то большую клику C Рис. 3.3: процесс перекрашивания для k = 4, i = j = 3.

i-ого цвета. И так далее: мы будем перекрашивать вершины пока не получим большую клику, часть вершин из которой мы уже рассматривали ранее в ходе этих перекрашиваний (см. рис. 3.3, где всего было сделано четыре перекрашивания и i = j = 3). Очевидно, что если на k + 1-ом шаге мы получили большую клику c какими-то вершинами из V (Cl vl ), где l k, то V (Ck+1 ) V (Cl vl ).

1.a) Пусть мы в конце вернулись к части клики C1, причем самих перекрашиваний было хотя бы три, то есть последняя раскраска была k, где k 3 (см. рис. 3.3). Попытаемся в изначальной раскраске 1 перекрасить в клике C1 какую-нибудь отличную от v1 вершину v в цвет j.

По утверждению 3.2.5 получится большая клика цвета j. Легко видеть, что эта клика содержит все вершины Ck кроме vk1, следовательно, любая вершина v C1, где v = v1, смежна со всеми вершинами в Ck кроме вершины vk1, так как v смежна с вершиной vk.

Отсюда можно сделать вывод, что любая вершина u Ck, где u = vk1, смежна со всеми вершинами из C1, кроме v1.

Перекрасим вершину v в раскраске 1 в j-ый цвет, а затем перекрасим некоторую вершину u из Ck, отличную от vk1 и vk, в i-ый цвет (мы так можем сделать, так как из определения i и j следует, что i 2 и j 2 ). Получим раскраску Gc с меньшим, так как u не смежна с v1 и смежна со всеми остальными вершинами из C1. Следовательно, данный случай невозможен.

1.b) Заметим, что если мы вернулись к части клики C1 и перекрашиваний вершин было всего два, то тогда вершина v2 смежна со всеми вершинами из клики C1, а значит при перекраске любой вершины из большой клики C1 в j-ый цвет мы получим по утверждению 3.2.5 новую большую клику j-ого цвета, содержащую V (C2 ) \ {v1 }. Таким образом, G(V (C1 ) V (C2 )) – полный граф. В силу произвольности выбора v1 и v2 и того, что граф G(V (C1 ) V (C2 )) – клика размера i + j + 1 в Gij, мы получаем, что вершины из множества V (C1 ) V (C2 ) не смежны с другими вершинами i-ых и j-ых цветов.

2) Если же мы вернулись в результате перекрашиваний к клике Cl, то исходя из всего выше сказанного (мы можем считать, что мы начали процесс перекрашивания с l ) G(V (Cl )V (Cl+1 )) образует клику в графе G. А тогда мы получаем l = 1, так как вершины из множества V (Cl ) V (Cl+1 ) не смежны с другими вершинами i-ого и j-ого цвета.

Замечание. Отметим, что в доказательстве утверждения 3.2.6 мы существенно пользовались тем, что i 2 и j 2. Иначе мы просто не смогли бы выбрать отличную от всех vi вершину.

Утверждение 3.2.7. В любой раскраске gc нет больших клик.

Доказательство. Пусть у этой раскраски есть большая клика C, например, первого цвета. Применим утверждение 3.2.6 к первому и второму цветам. Получим полный граф на вершинах цвета 1 и 2 размера 1 + 2 + 1 содержащий C. Заметим, что мы можем произвольным образом разбить этот полный граф на две части цветa 1 и 2 размера 1 + 1 и 2 соответственно, при этом полученная новая раскраска все равно будет лежать в. Используя утверждение 3.2.6 для первого и i-ого цвета (i [2, c + 1]) и предыдущее соображение легко доказать наличие в граc+ фе G полного подграфа на 1 + j вершине, то есть полного подграфа размера D + 1 – противоречие с условием теоремы 3.1.

Замечание. На самом деле мы только что доказали теорему 3.3. Также отметим, что искомая в теореме 3.3 раскраска задает разбиение всех вершин графа на нужные в следствии множества.

Замечание. Рассмотрим конкретную раскраску gc. Мы только что показали, что в раскраске gc нет больших клик. Таким образом, используя теорему Брукса, мы получим правильную раскраску каждого подграфа i-ого цвета в i цветов, в результате чего мы покрасим граф G правильным образом в D цветов ( i = D). Если какая-то вершина в раскраске gc была смежна с вершиной своего цвета, то по утверждению 3.2.4 у нее в окрестности (уже в раскраске в D цветов) будет хотя бы c + 1 различных цветов. То есть основная проблема заключается в раскраске “вырожденных” вершин, то есть вершин, несмежных со своим и еще каким-нибудь цветом, раскраски gc. Действительно, если бы G был изначально двудольным, теорема о его раскраске в D цветов с выполнением условия про “большое” количество различных цветов в окрестности каждой вершины была бы совсем неочевидной. На самом деле доказательство этой теоремы для случая двудольного графа весьма наглядно показывает, в чем собственно состоит сложность и специфика данной задачи, поэтому этот случай полезно иметь в виду.

Рассмотрим раскраску gc и рассмотрим в ней все вершины, которые смежны с вершинами не более чем c 1 различных цветов. Обозначим множество всех таких вершин. Заметим, что любая вершина v, во-первых, не смежна ни с одной вершиной своего цвета в раскраске gc, и, во-вторых, есть еще один отличный от цвета v цвет такой, что v не смежна ни с одной вершиной этого цвета. Таким образом, эту вершину v всегда можно перекрасить в другой цвет, так чтобы полученная новая раскраска по прежнему была из. Более того, можно перекрасить все или только часть вершин из некоторого i-ого цвета так, чтобы полученная раскраска по прежнему была из (естественно, перекрашивать мы их будем скорее всего в различные цвета).

Для любой вершины v найдется такой цвет в раскраске gc, что v соединена по крайней мере с вершинами этого цвета. Разобьем на c + 1 множество 1, 2,..., c+1, таким образом, что любая вершина Обозначим для всех i [1, c + 1] через Hi индуцированный подграф графа G на множестве вершин i-ого цвета в раскраске gc.

Утверждение 3.2.8. Для любой вершины v Hi верно следующее неравенство: dHi (v) + c+ Доказательство. Рассмотрим множество Ev всех ребер в графе G с одним концом в вершине v. Очевидно, что |Ev | D. Рассмотрим множество E1 Ev всех ребер из Ev, у которых смежная с v вершина не лежит Пусть из v ведет в некоторый цвет j отличный от i меньше, чем i dHi (v) ребер из множества E1 (см. рис. 3.4). Тогда перекрасим все вершины j-ого цвета множества i так, чтобы полученная раскраска по-прежнему была из. Очевидно, мы перекрасим эти вершины не в цвет i, поэтому величина dHi (v) в новой раскраске не изменит своего значения. Перекрасим в новой раскраске v в j-ый цвет. Заметим, что к значению для полученной раскраски добавится величина меньшая Тогда получаем, что всего из вершины v в графе G ведет по крайней мере R ребер, где По определению R |Ev | D. Получаем:

Используя то, что i [ c+1 ] и тот факт, что D (c3 + 8c2 + 19c + 3.2.2 Часть вторая.

Лемма 3.2.1. Пусть дано два непустых множества вершин A и B и некоторый связный граф H = (A B, E), обозначим через G индуцированный подграф H(B). Определим dA (v), где v B, как количество ребер ведущих из вершины v в множество A. Пусть граф H обладает следующими свойствами:

1) никакие две вершины множества A не соединены ребром;

2) степень каждой вершины из A в графе H по крайней мере q 3 + 3) для любой вершины v B выполняется неравенство:

Тогда можно раскрасить граф G правильным образом в d цветов так, чтобы для любой вершины v A среди ее соседей в B были вершины по крайней мере q различных цветов.

Замечание. (c + 2)3 + 2(c + 2)2 (c + 2) 8 = c3 + 8c2 + 19c + 6.

В лемме 3.2.1 множество вершин B обозначает то, что в части обозначалось как Hi, множество вершин A обозначает то, что раньше обозначалось как i, причем нам абсолютно все равно были ли между вершинами из i какие-нибудь ребра. Нам важно только с какими вершинами из Hi были смежны вершины из i, ибо красить мы будем только вершины из Hi.

Через q мы обозначим в лемме 3.2.1 то, что в части 1 было равно c + 2, а через d обозначим то, чему раньше было равно i. Через H в лемме 3.2.1 мы обозначим граф G(i Hi ) E(G(i )). По определению множества i из любой вершины v i вело по крайней меp полагать в лемме 3.2.1, что граф H связен (можно доказать все отдельно для каждой из компонент связности). Кроме того можно считать, что множество i не пусто, иначе мы получаем обычную теорему Брукса, так как тогда нам нужно всего лишь покрасить правильным образом граф Hi в i цветов, а мы знаем, что в графе Hi нет полных подграфов на i + 1 вершине (в графе Hi нет больших клик) и что 3.2.1 выполнены для множеств B = V (Hi ) и A = i.

Если мы, используя лемму 3.2.1 для множеств B = V (Hi ) и A = i, каждый подграф Hi графа G в раскраске gc раскрасим правильным образом в i новых цветов, так, что каждая вершина из i будет смежна с вершинами по крайней мере c различных цветов в графе Hi, то тогда мы получим правильную раскраску в D цветов всего графа G, при этом, как легко заметить, все вершины из множества = i будут смежны с вершинами по крайней мере c различных цветов. Кроме того в силу определения множества очевидно, что все вершины из множества V (G) \ будут смежны по крайней мере с c различными группами цветов, а значит и просто с c вершинами различных цветов. Таким образом мы свели теорему 3.1 к лемме 3.2.1 и нам осталось только доказать лемму 3.2.1.

Замечание. Вся вторая часть будет посвящена доказательству леммы 3.2.1. Поэтому, дабы избежать непонимания, связанного с совпадением обозначений, сразу оговорим то, что обозначения в части 1 и в части 2 не имеют никакой связи, то есть эти части автономны и не следует искать определения какой-нибудь величины из части 2 в части 1.

Замечание. В утверждении леммы 3.2.1 мы можем заменить q на q 2.

Но для удобства дальнейших выкладок мы этого делать не будем.

Доказательство Леммы 3.2.1. Предположим, что лемма не верна. Рассмотрим минимальный по количеству вершин граф H, удовлетворяющий всем условиям из леммы 3.2.1, для которого не верно утверждение леммы 3.2.1.

Определение 3.3. Назовем допустимым множество Si B, если Si NH (vi ), где vi A и |Si | = q. Множество всех возможных наборов выборок допустимых множеств Si по всем i {1, 2,..., |A|} будем обозначать как.

Утверждение нашей леммы вытекает из следующего факта:

Факт 3.2.1. Для каждой вершины vi из A мы сможем выбрать допустимое множество Si таким образом, что если добавить к ребрам E(G) все полные графы на множествах Si, то вершины полученного нового графа G можно раскрасить в d цветов правильным образом.

Замечание. Мы будем рассматривать G как граф с кратными ребрами.

Таким образом, мы получили равносильную переформулировку леммы 3.2.1. Для доказательства раскрашиваемости G в d цветов оказывается удобным проводить следующую редукцию графа.

Пусть в нашем графе G есть некоторая вершина v степени меньше d, тогда можно “выкинуть эту вершину из графа G и доказывать все уже для графа G \ v. Если мы сможем покрасить редуцированный граф, то потом мы всегда сможем докрасить v по принципу Дирихле в свобобный цвет.

Определение 3.4. Будем говорить, что v рекурсивно удаляется из графа G, если можно провести последовательность таких редукций, чтобы последней в этой последовательности редуцировалась вершина v. А граф G будем называть рекурсивным, если он последовательно редуцируется до пустого графа.

На самом деле мы будем доказывать более сильный факт, а именно:

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

Вернемся к доказательству нашей леммы, а точнее к доказательству последней переформулировки факта 3.2.1. Обозначим через S множество тех вершин из B, которые смежны хотя бы с одной вершиной из Докажем, что для графа H будет выполнена усиленная переформулировка факта 3.2.1, в предположении, что H минимальный по количеству вершин граф, для которого не верна лемма 3.2.1. Таким образом мы получим противоречие, а значит докажем лемму 3.2.1.

Определение 3.5. Определим для каждой вершины v из множества B величину Факт 3.2.2. Заметим, что если выбрать Si случайным образом (независимо для каждой вершины vi, причем для каждой вершины vi все возможные варианты множества Si равновероятны), то математическое ожидание степени каждой вершины v из множества S в графе G будет не больше dG (v) + dA (v)(q 1) q3 +2qq q8, то есть не более L(v) (так как q 4, то q 3 + 2q 2 q 8 > q(q 2 1)), а значит по третьему условию леммы 3.2.1 меньше d. Таким образом, в среднем степень каждой вершины в G будет меньше d. А это дает нам надежду на то, что граф G окажется рекурсивным, то есть, если мы последовательно будем удалять из G вершины степени меньше чем d, мы в конце концов получим пустой граф.

Для завершения доказательства леммы нам осталось удачно выбрать Si (т.е выбрать так, чтобы G стал рекурсивным).

Определение 3.6. Сдвигом нескольких допустимых множеств Si1, Si2,...,Siz в выборке назовем замену на, где отличается от только тем, что все допустимые множества Si1,..., Siz заменены в ней на некоторые другие допустимые множества Si1,..., Siz. Множества Si1,..., Siz будем называть результатом сдвига множеств Si1, Si2,..., Siz.

Обозначим через R множество B \ S. Можно считать, что степень любой вершины из R равна d, так как по условию леммы 3.2.1 степень любой вершины из B в графе G меньше либо равна d, а если степень вершины меньше d, то можно сразу выкинуть рекурсивно эту вершины из G, для любой допустимой выборки.

Утверждение 3.2.9. Пусть дан граф F такой, что V (F ) = F1 F и F1 F2 =. Степень любой вершины из F2 в графе F меньше либо равна D и в F существует вершина v F1, что • граф F (F2 {v}) связен, • v смежна со всеми остальными вершинами в F1.

Пусть кроме того, граф F (F1 ) уже раскрашен правильным образом в D цветов. Тогда имеющуюся раскраску можно дополнить до правильной раскраски графа F в D цветов.

Доказательство. Выкинем из графа F (см. рис. 3.5) вершину v, получится новый граф F. На множестве F1 \ {v} уже есть правильная раскраска в D цветов. По одной вершине рекурсивно докрасим правильным образом все вершины из F2, так можно сделать в силу связности графа F (F2 {v}) и условия, что степень в графе F любой вершины из F меньше либо равна D. Перенесем полученную правильную раскраску графа F в D цветов на F и покрасим v в какой-нибудь цвет отличный от всех цветов вершин из NF (v) (так можно сделать, так как по условию dF (v) < D). В итоге мы покрасили правильным образом в D цветов граф F, правда при этом мы возможно изменили цвет у вершины v по сравнению с заданной раскраской на F1. Заметим, что все вершины из множества F1 \ {v} будут покрашены в цвета отличные от цвета v в исходной раскраске F1, так как эта раскраска была правильной для графа F (F1 ), а вершина v смежна со всеми остальными вершинами в F1, кроме того заметим, что все цвета вершин из множества F1 \ {v} отличны от цвета v в раскраске F. Теперь, если мы изменили цвет у вершины v по сравнению с исходной раскраской F1, то просто поменяем цвет, совпадающий с цветом v в исходной раскраске F1, и нынешний цвет v в раскраске F местами. Получится опять правильная раскраска F, но уже полностью совпадающая с исходной раскраской на множестве Определение 3.7. Регулярным сдвигом множеств Si, некоторого набора относительно множества S мы будем называть такой сдвиг множеств Si, где i [1, |A|], в множества Si, i [1, |A|], что для всех i [1, |A|] множество Si S содержит множество Si S. Если найдется i [1, |A|], что |Si S | строго больше |Si S |, то такой регулярный сдвиг мы будем называть невырожденным.

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

Утверждение 3.2.10. Пусть есть набор допустимых множеств = {S1, S2,..., S|A| } графа H минимального по количеству вершин контрпримера к лемме 3.2.1, и пусть есть такие множества S S, R R, что все вершины из B \(S R ) рекурсивно удаляются из графа G, причем для всех u R dG (u) = d и для всех u R dG(S R ) (u) = d.

Кроме того пусть H := G(S R ) и Тогда можно регулярно сдвинуть невырожденным образом несколько множеств Si относительно множества S R, так чтобы B \(S R ) по-прежнему рекурсивно удалялось уже из полученного в результате этого сдвига графа G.

Доказательство. Доказывать это утверждение мы будем индукцией по размеру множества B \ (S R ).

База случай: |B \ (S R )| = 0 очевидно невозможен, так как в силу факта 3.2.2 не будет выполнено условие (2).

Переход от всех меньших, чем k, размеров множества B \ (S R ) к размеру k.

Пусть Z := B \ (S R ) (см. рис. 3.6).

Пусть у нас есть множества S и R такие, что |Z| = k и для них не выполнено утверждение индукционного перехода.

Покажем, что существует такая вершина vi A и соответствующее ей множество Si, что Si можно регулярно сдвинуть относительно S невырожденным образом. Предположим противное, тогда для любого допустимого множества Si и соответствующей ему вершины vj A допускается всего две возможности:

1) множество Si S = (см. рис. 3.7);

2) множество NH (vi ) \ S Si (см. рис. 3.8).

Как нетрудно заметить, количество добавленных ребер с концами в множестве вершин S в обоих этих случаях достигает своего минимальdH (v) ного значения. Таким образом верна цепочка неравенств математическое ожидание случайной величины (с оговоренным в факте 3.2.2 распределением). Мы знаем из условия (2), что dH (u) > L(u). Получаем противоречие с предыдущим неравенством.

Значит все-таки есть такая вершина vi A, что часть ее окрестности находящаяся в Z не лежит в соответствующем множестве Si, а множество Si S =.

Таким образом мы можем рассмотреть такую вершину v NH (vi ), что она не лежит ни в множестве S, ни в множестве Si, при этом часть множества Si лежит в множестве S. Мы знаем, что Z рекурсивно удаляется из G. Начнем удалять рекурсивно вершины из Z, причем будем рекурсивно удалять пока это возможно вершины отличные от v. В какойто момент мы не сможем ничего удалить, кроме v. Это значит, что от множества Z остались вершины v, u1, u2,..., ul S, w1, w2,..., wm R (см. рис. 3.9).

Обозначим множество всех оставшихся в Z вершин через P, а через I обозначим индуцированный граф G(S R P ).

Заметим, что степени в графе I всех вершин uk, где k [1, l], и всех вершин wj, где j [1, m], по крайней мере d.

Заметим также, что степень вершины v в I меньше d.

Если степень вершины v меньше d q + 1, то сдвинем Si в множество Si следующим образом: возьмем вершину x из Si, которая лежит в множестве S Si (такая вершина x обязательно найдется, т.к. S Si = ), тогда Si := (Si \ {x}) {v}. Остальные множества из набора мы двигать не будем. Заметим, что описанный нами сдвиг будет регулярным и невырожденным относительно множества S, также понятно, что множество Z по-прежнему можно рекурсивно удалить (очевидно, что можно также как и раньше рекурсивно удалить все вершины из Z \ P, потом можно рекурсивно удалить вершину v, т.к. степень вершины v в графе I была меньше d q + 1, а значит после сдвига стала не более d 1, а потом можно рекурсивно удалить оставшиеся в Z вершины, т.к. множество Z рекурсивно удалялось из графа G и новых ребер в графе I {v} при описанном выше сдвиге не добавилось). В этом случае мы доказали индукционный переход.

Предположим противное, пусть степень v меньше d, но по крайней мере d q + 1.

Докажем, что уже для графа I выполнено неравенство Пусть мы доказали это, тогда мы можем применить предположение индукции для множеств S0 и R0, где S0 := (S R P ) S и R0 := (S R P ) R, то есть мы можем регулярно сдвинуть невырожденным образом набор множеств относительно S R P, так чтобы вершины из B \ (S R P ) по-прежнему удалялись рекурсивно в полученном графе. Заметим, что если набор сдвинулся регулярно относительно S R P, то он сдвинулся регулярно относительно S R.

Кроме того заметим, что в полученном в итоге сдвига графе будут попрежнему рекурсивно удаляться все вершины из множества B \(S R ), так как мы можем вначале рекурсивно удалить все вершины множества B \ (S R P ), а затем удалить рекурсивно все вершины из P, благо что новых ребер в графе I в результате такого сдвига не добавилось.

Мы будем так делать пока одно из множеств Si регулярно не сдвинется невырожденным образом относительно S R, либо пока степень вершины v не станет меньше dq +1, либо степень какой-то вершины из P \ {v} не станет меньше d. В последнем случае мы рекурсивно сможем еще выкинуть несколько вершин из Z и уже для нового меньшего графа I применить те же самые рассуждения. Здесь необходимо отметить, что рано или поздно мы обязательно прийдем к одному из этих вариантов, так как иначе мы будем бесконечное число раз делать регулярный невырожденный сдвиг относительно множества S R P, а значит сколь угодно долго уменьшать значение суммы Обозначим через l количество ребер, ведущих из множества вершин P в множество вершин S.

В силу условий утверждения 3.2.10, что для всех u dG(S R ) (u) = d, и что для всех u R dG (u) = d, не может быть ребер между множествами P и R.

Для завершения доказательства утверждения 3.2.10 осталось доказать, что для графа I = G(S R P ) выполнено неравенство (2 ).

Предположим противное. Тогда То есть мы получаем, что А значит мы получаем неравенство:

Оценим величину dI (ui ) L(ui ) для всех i [1, l].

По определению L(u) и в силу того, что dI (ui ) d получаем, что для Используя неравенство (1) получим:

для всех i [1, l], так как ui S для всех i [1, l]. Рассмотрим два случая:

В обоих случаях выполнено неравенство:

Пусть q1 := dI (v) d + q, тогда, как мы показали выше, q1 > 0.

Заметим, что для вершины v аналогично выкладкам ( ) и (4) можно получить неравенство Так как wi R, где i [1, m], то тогда dG (wi ) = L(wi ), кроме того вершины из множества P R нельзя рекурсивно удалить из графа I.

Используя еще условие утверждения 3.2.10, что для любой вершины u R dG (u) = d, мы получаем dI (wj ) = dG (wj ) = d. А тогда для всех i [1, m] верно равенство:

Подставим теперь неравенства (4), (5) и равенство (6) в неравенство (3). Получим неравенство:

2. Нахождени блоков в G. Находит представление каждого блока в виде множества его вершин.

3. Поиск цвета различающего пару (u, v). Требует от нас ввести один бинарный массив C размера c|E(G)|, который мы будем использовать многократно при каждом применение процедуры.

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

Теперь мы наконец готовы дать описание нашего алгоритма.

• ШАГ 1. Пускай найдется вершина v V с |L(v)| > degG (v). Процедура рекурсивного удаления вершин выдаст нам искомую раскраску и в этом случае мы закончим выполнение алгоритма.

• ШАГ 2. A) Находим все блоки в G и строим дерево блоков и точек сочленения T.

1. Находим блоки G используя процедуру поиска блоков.

2. Для кажой вершины v графа находим список блоков, содержащих v.

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

• B) Берем последний блок B в порядке B и единственную точку сочлнения в этом блоке v0. В следующих шагах мы пытаемся уменьшить G удалив вершины B \ {v0 }, или найти желаемую раскраску.

• ШАГ 3. Пытаемся найти в B пару различимых некоторым цветом вершин (u, v) таких, что u не является точкой сочленения, т.е. u = v0.

1. Если в B имеется такая пара вершин (u, v) различимых цветом c, тогда мы красим u в цвет c и удаляем ее из G. В оставшемся графе |L(v)| > deg(v), кроме того G = G \ {u} связен. Находим раскраску G с помощью процедуры рекурсивного удаления вершин и завершаем работу.

2. Иначе мы переходим к следующему шагу.

• ШАГ 4. Проверяем является ли блок B кликой или нечетным циклом. Это можно легко проверить предварительно посчитав степени всех вершин в G.

1. Если B является кликой или нечетным циклом, мы уменьшаем G удаляя B \ {v0 }. Из за того, что в ШАГЕ 3 v0 и любая вершина v блока B смежная с v0 не различимы никаким цветом, мы имеем L(v0 ) L(v). Удалим из списка L(v0 ) список L(v). Затем вернемся к ШАГУ 2 B) и применим его к идущему до B в порядке B блоку. В этом месте алгоритма мы пользуемся свойством порядка B, чтобы эффективно уменьшить L(v0 ).

2. Другие варианты для B. В этом случае мы обязательно получим желаемую раскраску и завершим работу.

– Раскрасим G(V \ V (B)) применив процедуру рекурсивного – Удалим из L(v0 ) все цвета, в которые покрашены соседи v0.

– Проверим одинаковые ли списки допустимых цветов у v0 и – Если эти списки разные, тогда пара (v0, u) для оставшихся не покрашеных вершин будет различима некотрым цветом.

Дополним раскаску всего графа аналогично ЩАГУ 3.1 и завершим работу.

– В противном случае применим процедуру -раскраски к B.

4.2.2 Реализация процедур Здесь мы подробно описываем наши вспомогательные процедуры и проводим анализ сложности их работы.

Рекурсивное удаление вершин Пусть есть v V с |L(v)| > degG (v). Поместим вершину v в стек O и удалим ее из графа.

В оставшемся графе опять найдется вершина удовлетворяющая тому же самому свойству, так как G связен и |L(u)| deg(u) для каждой вершины u V. Повторим предыдущее действие для новой вершины, т.е. поместим ее в O и удалим из G. Продолжим удалять вершины до тех пор, пока в G не останется вершин.

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

Замечание. Процедуру можно с тем же успехом применять и для графов имеющих более одной компоненты связности, если в каждой компоненте есть вершина w, для которой выполнено неравенство |L(w)| > deg(w).

Утверждение 4.2.1. Рекурсивное удаление вершин в G и последующая раскраска работают за линенйное от размера графа время.

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

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

Чтобы покрасить все вершины в O за линейное время, достаточно покрасить данную вершину u O за время O(|L(u)|).

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

На стадии раскраски вершины u в нашей процедуре мы помечаем в C0 те цвета, в которые уже покрасили соседей u, и затем ищем в L(u) цвет c со значением 0 в C0 [c]. После того как мы нашли c, мы обнуляем C0, проходя один раз по всем соседям u. Таким образом, мы возвращаем C в изначальное состояние и можем использовать его для других вершин.

После этого мы красим u в цвет c. Завершая доказательство отметим, что для раскраски u мы использовали времени O(|L(u)|); также всего мы использовали c|E(G)| памяти, так как создали массив такого размера всего один раз.

Поиск блоков в G.

Алгоритм нахождения всех блоков в графе за линейное время можно найти, напримар, в [26].

Поиск цвета различающего пару (u, v).

Нам понадобится еще один массив C инициализированный 0, аналогичный массиву C0. В нем мы пометим 1 все цвета встречающиеся в L(v) и затем проверим есть ли цвет c в L(u) для которого C[c] равно 0; в конце процедуры заменим все 1 назад на 0. В итоге мы либо находим различающий цвет, либо убеждаемся, что такого цвета нет, за линейное от |L(u)| + |L(v)| время.

Нахождение -раскраки связного графа.

Мы будем использовать линейный по времени алгоритм Ловаша [23] находящий -раскраску за линейныое время. Существует более простой альтернативный алгоритм, который мы описываем в Секции 4.3 и из которого также легко получается конструктивное доказательство теоремы Брукса.

4.2.3 Доказательство корректности алгоритма ШАГ 1. Мы вычисляем степени всех вершин в G и для каждой вершины проверяем |L(v)| > degG (v).

A) Нахождение всех блоков в G и построение дерева блоков и точек сочленения T. В нашем представлении блоков каждый блок описывается как множество вершин; также для каждой вершины мы строим список блоков ее содержащих. Напомним определение дерева блоков и точек сочленения. Рассматривается двудольный граф H, у которого одна доля состоит из всех возможных блоков, а дугая из всех точек сочленения (то есть вершин входящиз по крайней мере в два блока) и E(H) = {(B, v) | v B}; по построению H является деревом и называется деревом блоков и точек сочленения. Из-за соображений сложности вычислений нам понадобится построить T как дерево обхода в ширину, т.е. мы требуем, чтобы T имело определенный порядок на блоках и точках сочленения.

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

Для представления дерева удобно рассмотреть ориентацию по направлению к корню. Для этого мы добавляем искуственную вершину в G и соединяем ее с произвольной вершиной. Таким образом мы добавляем искуственный блок B0 в T. Возьмем B0 и рассмотрим порядок B, в котором появляются блоки при поиске в ширину на дереве T с корнем в B0.

B) Пусть B последний блок дерева T в порядке B.

Отметим, что B является висячим блоком. Обозначим через v0 точку сочленения B, т.е. единственную точку сочленения в T соединенную с B.

Так как B стоит в конце B и порядок B соответсвует обходу в ширину, все оставшиеся соседи v0, появляющиеся после v0 в B, являются висячими блоками.

ШАГ 3. Случай A. Предположим мы нашли упорядоченную пару вершин (u, v) различимых цветом c, такую что u не является точкой сочленения в блоке B. Тогда мы красим u в цвет c и удаляем ее из G.

В оставшемся графе, |L(v)| > deg(v). Кроме того G = G \ {u} связен, так что мы можем покрасить G с помощью процедуры рекурсивного удаления вершин.

Случай B. Если такой пары нет, то для всех вершин не точек сочленения w, v B имеем L(v) = L(w), в то время как для точки сочленения v0 имеем L(v0 ) L(v). Следовательно, все вершины B \ {v0 } имееют одинаковую степень, тогда мы переходим к ШАГУ 4.

На следующем шаге алгоритма мы либо уменьшим G отрезав B \ {v0 }, либо найдем раскрасим G с помощью процедуры рекурсивного удаления вершин.

ШАГ 4. Списки цветов всех вершин не точек сочленения B одинаковы и содержатся в списке цветов точки сочленения B.

Согласно теореме Брукса [14] (см. Замечание 4.1.2) существует два случая, которые можно различить с помощью предварительного подсчета степеней вершин.

Случай I (B является кликой или нечетным циклом) Производить редукцию списка L(v0 ) нужно очень осторожно из за того, что |L(v0 )| может быть гораздо больше, чем размер B. Мы опишим этот момент подробно в Секции 4.2.4.

Случай II (Другие варианты для B.) В этом случае согласно классификации Ердеша и других [16], мы знаем, что G обязан иметь правильную раскраску для любого набора списков.

4.2.4 Анализ сложности алгоритма Ясно, что ШАГИ 1 и 2 занимают всего O(|G| + |L|) времени.

ШАГ 3.

Часть 1. Поиск пары различимых некоторым цветом вершин в B \{v0 }.

Утверждение 4.2.2. Поиск пары различимых некоторым цветом вершин (u, v), таких что u, v = v0, может быть сделан за линейное от размера блока время, где под размером блока мы подразумеваем число ребер плюс число вершин в данном блоке.

Доказательство. Мы можем рассмотреть остовное дерево поиска в глубину блока B с корнем в v0 и проверить только пары списков допустимых цветов для смежных вершин в этом дереве. Так как B является блоком, v0 имеет единственного соседа в таком дереве. Таким образом для каждой пары смежных вершин u и v мы дважды применяем процедуру поиска различающего цвета, сначала для (u, v) потом для (v, u).

Теперь покажем, что общее время всех проверок линейно по отноL(v)|. Проверяя вершины u и v, которые не являются шению к точками сочленения, мы либо получаем, что L(u) = L(v), либо находим упорядоченную пару вершин и различающий их цвет. В последнем случае мы заканчиваем поиск пар. В первом же случае легко видеть, что проверка работаут за линейное от min(|L(u)|, |L(v)|) время. Таким образом общее время работы будет линейным от Часть 2. Проверка различимы ли (u0, v0 ) некоторым цветом за линейное от L(u0 ) время, где u0 смежна с v0 в B.

Замечание. Нам нужно сделать только одну проверку для v0 и ее единственного соседа в дереве потому, что B является блоком и мы рассматриваем дерево поиска в ширину с корнем в v0. Но мы не можем позволить себе сделать такую проверку за линейное от |L(v0 )| + |L(u0 )| время непосредственным образом для всех блоков висящих на v0. Из за того, что |L(v0 )| может быть намного больше, чем размер B, и более того, v0 может быть точкой сочленения для многих маленьких блоков включая B, общее время работы может иметь квадратную ассмиптотику по отошению к размеру входа, например для G = Kn1,1. По тем же причинам мы не можем непосредственным образом редуцировать L(v0 ) в Шаге 4.

Чтобы избежать многократных проверок описанных в Замечании 4.2.4 и редукций L(v0 ) для большого L(v0 ) мы можем запомнить 1 значения L(v0 ) в C и использовать их не только для одного висящего на v0 блоке, но сразу для всех таких блоков. Строго гоовря мы делаем следующее:

• Вводим с самого начала работы алгоритма новый бинарный массив C с |C | = |C|, изначально заполненный 0.

• Если точка сочленения висячего блока B отличается от предыдущей, скажем v0, тогда мы делаем следующее.

1. Возвращаем C в изначальное состояние с одними 0 за линейное от |L(v0 )| время, проходя один раз по спику L(v0 ).

2. Помечаем 1 в C цвета L(v0 ).

• Для висячего блока B и точки сочленения v0 проверяем пару (u0, v0 ) за линейное от |L(u0 )| время. Это можно сделать лишь за один проход по L(u0 ) проверяя стоит ли 1 в C [c] для c L(u0 ).

Чтобы найти различающий цвет для пары (u0, v0 ), можно вместо L(v0 ) использовать C, так как поиске различающей пары мы проверяем только принадлежит ли цвет i L(u0 ) списку L(v0 ).

ШАГ 4.

Эффективная редукция L(v0 ). При любой редукции мы будем эффективно поддерживать только C вместо L(v0 ), так как нам не нужен целый список L(v0 ), если v0 является точкой сочленения. Таким образом при каждой редукции L(v0 ) мы просто помечаем назад 0 все цвета L(u0 ) в C и пока не меняем L(v0 ). Реально мы изменим L(v0 ) только когда обрежим все висячие блоки содержащие v0 и когда v0 перестанет быть точкой сочленения. В силу определения B мы сделаем такую замену только один раз для v0 и следовательно общее время потраченное на редукцию списков для всех точек сочленение займет линейное время.

После описанной выше “воображаемой” замены L(v0 ) мы раскрасим все вершины в B \{v0 } и удалим их из G. Затем вернемся назад к Шагу 2 B) и найдем следующий висячий блок в редуцированном графе.

Следовательно, в Шаге 3 и Шаге 4 алгоритм работает за время O(|B|) для каждого отдельного блока B и поддержка C для каждой точки сочленения в сумме будет работать за время O(|L|). Складывая написанное выше, мы видим, что алгоритм работает за линенйное от O(|G| + |L|) время.

4.3 Конструктивное доказателсьво теоремы -раскраска двусвязного графа, который не является ни кликой ни нечетным циклом. Здесь мы опишем алгоритм отличный от Шага 4 III. Мы можем считать, что все вершины в B \ {v0 } (v0 является единственной точкой сочленения в B) имееют один и тот же список допустимых цветов. Следовательно все вершины в B \ v0 имееют одинаковую степень.

К этому моменту мы уже знаем, что B является блоком, т.е. двусвязным графом. Более того, мы уже нашли остовное дерево в B с порядком обхода поиска в глубину (это дерево является частью поиска в глубину для графа G) и описали процедуру рекурсивного удаления вершин. Используя все это мы теперь можем описать доволнь простой алгоритм для раскраски G. Единственная трудность алгоритма заключается в числе комбинаторных случаев, которые нам придется рассмотреть. Такми образом описывать алгоритм мы будем в порядке рассмотрения и разбора случаев следующим образом.

• Пусть у нас имеется две несмежные вершины, скажем u и v, в B\{v0 } такие, что если мы сделаем следующее:

– покрасим u и v в один и тот же цвет – удалим этот цвет из L(w) для каждого соседа w вершины v или – удалим обе вершины u и v из G, то к оставшемуся графу будет применима процедура рекусивного удаления вершин. Назовем такую пару вершин u и v хорошей парой.

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

• Если degG (u) = 2 для некоторой вершины u B \ {v0 }, тогда B является циклом и мы знаем, что B не может быть нечетным циклом.

Следовательно, B явялется четным циклом. Раскрасим B \ {v0 } и удалим из L(v0 ) цвет двух соседей v0 в B и затем раскрасим оставшийся граф используя процедуру рекурсивного удаления вершин.

• Если в нашем дереве поиска в глубину, т.е. нормальном дереве с корнем в v0, есть вершина u имеющая двух потомков, то эти два потомка будут хорошей парой. Действительно, лекго показать в силу того, что дерево с корнем в v0 нормальное, что эти два потомка не смежны. Также не трудно убедиться, что удалив из B этих двух потомков, в оставшемся графе всегда найдется путь от u до любой другой вершины. Из этих двух соображений вытекает хорошесть пары.

• Если наше дерево поиска в глубину не является простым путем, тогда мы можем эффективно, т.е. за линейное от размера блока время, найти такую пару. В последнем случае, мы завершаем работу.

• Таким образом наше дерево представляет из себя простой путь w0, w1, w2,..., wk1, v0, где v0, как упоминалось выше, является единственной точкой сочленения блока B в графе G. Для удобства обозначений, пусть v0 = wk. Рассмотрим ближайшую к w0 вершину, скажем wt, на этом пути, которая не смежна с w0, и следовательно degG (w0 ) t 1 (отметим, что такая вершина wt обязательно найдется, так как блок B не является кликой и степени всех вершин в нем равны).

w1, w2,..., wt1 есть вершина, смежная с чем-то отличным Последнее выполненяется в виду того, что w0 и wt не смежны и в графе B \ {w0, wt } не может быть более двух компонент связности, так как w0 является висячей вершиной в нормальном дереве (wt1 была смежна сразу с w0 и wt и вершины w1, w2,..., wt будут связны в B \ {w0, wt }, также как v0 будет связана со всеми остальными вершинами).

2. Пусть degG (w0 ) t + 1, тогда w1 смежна с некторой вершиной wl, где l t + 1, так как degG (w1 ) = degG (w0 ) t + 1, и, следовательно, мы нашли хорошую пару согласно случаю 1.

3. Если t 1 = degG (w0 ), тогда wt1 не смежна с некоторой вершиной wr, где r < t 1, потому, что degG (w0 ) = degG (wt1 ) и wt смежна с wt. Значит wr и wt1 образуют хорошую пару, так как 4. Предположим, что t = degG (w0 ) и мы не в условиях случая 1.

смежна с wt и wt+1 и есть вершина wi смежная с w0, где i > t. Мы можем считать, что i > t + 1, так как вариант, когда i = t + 1, мы рассмотрели в случае 1. Значит, так как degG (wt ) = degG (w0 ) > 2, wt1 и wt+1 образуют хорошую пару.

Замечание. Тот же самый алгоритм работает для -раскраски двусвязного графа H. Действительно, можно взять произвольную вершину H в качестве точки сочленения v0, после чего раскрасить H за линейное от размера H время, в случае, если есть вершина u с degH (u) < (H).

Замечание. Из этого алгоритма также вытекает доказателство теоремы Брукса [14] для двусвязных графов, так как если граф не клика и не нечетный цикл, можно применить наш алгоритм и получить правильную раскраску.

Благодарности. Мы благодарим Олега Бородина и Александра Косточку за указание весьма полезных ссылок на литературу.

Литература [1] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976.

[2] R. L. Brooks, On coloring the nodes of network, Proc. Cambridge Philos.

Soc. 37 (1941) 194-197.

[3] L. Hong-Jian, B. Montgomery, Hoifung Poon, Upper Bounds of Dynamic Chromatic Number, Ars. Combinatoria 68(2003), pp. 193-201.

[4] B. Montgomery, Dynamic Coloring, Ph.D. Dissertation, West Virginia University, 2001.

[5] X. Meng, L. Miao, Z. R. Li, B. Su, The Conditional coloring numbers of Pseudo-Halin graphs, Ars Combinatoria 79(2006), pp 3-9.

[6] Suohai Fan, Hong-Jian Lai, Jianliang Lin, Bruce Montgomery, Zhishui Tao, Conditional colorings of graphs, Discrete Mathematic 16(2006),1997-2004.

[7] H. Hind, M. Molloy, B. Reed, Colouring a graph frugally, Combinatorica 17(4) (1997) 469-482.

[8] Godsil C., Royle G. Algebraic graph theory (Springer, 2001)(L)(T)(ISBN 0387952411).

[9] L. Lovasz, On decomposition of graphs, Studia Sci. Math. Hungar. (1966) 237-238.

[10] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.

[11] O. V. Borodin, A chromatic criteria for degree assignment, IV USSR conference on the theoretical cybernetics problems, in Novosibirsk, proceeding reports, 127-128 (1977) (in Russian) [12] O. V. Borodin, Problems of colouring and of covering the vertex set of a graph by induced subgraphs, Ph.D. Thesis, Novosibirsk State University, Novosibirsk, 1979 (in Russian).

[13] O. V. Borodin, A. V. Kostochka, On an upper bound on a graph’s chromatic number, depending on the graphs’s degree and density J.

Comb. Th. (B) 23 (1977), p. 247-250.

[14] R. L. Brooks, On colouring the nodes of network, Proc. Cambridge Phil.

Soc. 37 (1941) 194–197.

[15] R. Diestel Graph Theory, Springer, Berlin Heidelberg New York, 2000.

[16] P. Erds, A. L. Rubin, H. Taylor, Choosability in graphs, in: Proc. Westo Coast Conf. on Combinatorics, Graph Theory and Computing, Arcata, California, Congr. Numer. XXVI (1979) 125–157.

[17] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci. (1963) p. 373-395.

[18] T. R. Jensen, B. Toft, Graph Colouring Problems, John Wiley & Sons, New York, 1995.

[19] Kawarabayashi, Ken-ichi, B. Mohar, List-color-critical graphs on a xed surface, SODA ’09: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 1156–1165, New York 2009.

[20] A. Kostochka, M. Stiebitz, A list version of Dirac’s Theorem, J. Graph Th. 39 (2002).

[21] A. Kostochka, M. Stiebitz, B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math 162 299-303 (1996) [22] J. Kratochv Z. Tuza, M. Voigt, New trends in the theory of graph colorings: choosability and list coloring, 183–197, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 49, Amer. Math. Soc., Providence, RI, [23] L. Lovsz, Three short proofs in graph theory, J. Comb. Th.(B) 19(1975), 269–271.

[24] B. Reed, A strengthening of Brooks’ theorem, J. Comb. Th. (B) V. 76, (1999) p. 136 - 149.

[25] S. Skulrattanakulchai, -List Vertex Coloring in Linear Time and Space, Information Processing Letters, Vol. 98, Issue 3 (May 2006), 101–106.

[26] R. Tarjan, Depth-rst search and linear graph algorithms, SIAM J.

Comput. 1 (2) (1972) 146–160.

[27] Z. Tuza, Graph colorings with local constraints a survey, Discussiones Math. Graph Th. 17(2) (1997), 161– [28] В. Визинг, Colouring the vertices of a graph in prescribed colours., Metody Diskret. Anal. v Teorii Kodov i Schem 29 (1976), 3–10 (In Russian) [29] http://www1.spms.ntu.edu.sg/~ngravin/code/Dcols.tgz



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

«БАГЛУШКИНА Светлана Юрьевна ГИГИЕНИЧЕСКАЯ ОЦЕНКА ФАКТОРОВ РИСКА АРТЕРИАЛЬНОЙ ГИПЕРТЕНЗИИ У ВЗРОСЛОГО НАСЕЛЕНИЯ 14.02.01 – гигиена 14.01.04 – внутренние болезни ДИССЕРТАЦИЯ на соискание ученой степени кандидата медицинских наук Научные руководители: доктор медицинских наук Тармаева Инна...»

«А.И.Клюкина МЕТОДОЛОГИЯ И ПРАКТИКА РЕАЛИЗАЦИИ ПЕДАГОГИЧЕСКОГО ПОТЕНЦИАЛА МУЗЕЯ (На примере музеев естественнонаучного профиля) Специальность 13.00.05 – Теория, методика и организация социально-культурной деятельности Диссертация на соискание ученой степени доктора педагогических наук Санкт – Петербург 2014 год 1 СОДЕРЖАНИЕ Введение Стр. Актуальность и степень разработанности проблемы. Цель. Задачи. Объект. Предмет исследования. Методология, методика, организация, база...»

«БИКСОЛТ АЛЕКСАНДРА МОИСЕЕВНА ОРГАНИЗАЦИОННО-ПРАВОВЫЕ МЕХАНИЗМЫ ОГРАНИЧЕНИЯ КУРЕНИЯ ТАБАКА В РОССИЙСКОЙ ФЕДЕРАЦИИ 14.02.03. Общественное здоровье и здравоохранение Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : академик...»

«Абдулаева Софья Вячеславовна Лазерный липолиз в пластической хирургии 14.01.17 - хирургия Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель д.м.н., профессор Данилин Н.А. Москва 2014 г. 0 ОГЛАВЛЕНИЕ Введение..4-8 Глава 1. Обзор литературы 1.1 Современное состояние вопроса обьемной и контурной коррекции тела.. 1.2 Анатомия жировой...»

«Черемохов Алексей Юрьевич УДК 533.6.011.51+533.6.011.72+532.529.5 ВЗАИМОДЕЙСТВИЕ УДАРНЫХ ВОЛН С ТЕПЛОВЫМИ И МЕХАНИЧЕСКИМИ НЕОДНОРОДНОСТЯМИ (01.02.05 - механика жидкости, газа и плазмы) Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : доктор физико-математических наук, профессор КОВАЛЕВ Ю.М. Челябинск - СОДЕРЖАНИЕ...»

«Мухаммед Ариж Абделькаримовна ИССЛЕДОВАНИЕ ГИПОЛИПИДЕМИЧЕСКИХ СВОЙСТВ ВЕЩЕСТВ ПРИРОДНОГО ПРОИСХОЖДЕНИЯ НА ОСНОВЕ ЧЕСНОКА, РАСТИТЕЛЬНЫХ МАСЕЛ И ПИЩЕВЫХ ВОЛОКОН (Экспериментальное исследование) 14.03.06 – фармакология, клиническая фармакология Диссертация на...»

«Дмитриев Максим Эдуардович Амино- и амидоалкилирование гидрофосфорильных соединений (02.00.03 – органическая химия) Диссертация на соискание ученой степени кандидата химических наук Научный руководитель : кандидат химических наук, ведущий научный сотрудник В.В.Рагулин Черноголовка ОГЛАВЛЕНИЕ ВВЕДЕНИЕ Актуальность работы Научная новизна и практическая...»

«Денисова Марина Николаевна РАЗРАБОТКА ГИДРОТРОПНОГО СПОСОБА ПОЛУЧЕНИЯ ЦЕЛЛЮЛОЗЫ ИЗ НЕДРЕВЕСНОГО РАСТИТЕЛЬНОГО СЫРЬЯ Специальность 05.21.03 – Технология и оборудование химической переработки биомассы дерева; химия древесины Диссертация на соискание ученой степени кандидата технических наук НАУЧНЫЙ РУКОВОДИТЕЛЬ, кандидат...»

«КАЗАНЦЕВА МАРГАРИТА ВИКТОРОВНА НАУЧНОЕ ОБОСНОВАНИЕ НАПРАВЛЕНИЙ СОВЕРШЕНСТВОВАНИЯ ОРГАНИЗАЦИИ ОНКОЛОГИЧЕСКОЙ ПОМОЩИ НА РЕГИОНАЛЬНОМ УРОВНЕ 14.02.03 – Общественное здоровье и здравоохранение Диссертация на соискание ученой степени доктора медицинских наук Научный консультант : д.м.н., профессор Линденбратен А.Л. Москва - 2014 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ.. ГЛАВА I. ЭПИДЕМИОЛОГИЧЕСКАЯ СИТУАЦИЯ ПО ОНКОЛОГИЧЕСКОЙ ЗАБОЛЕВАЕМОСТИ В МИРЕ И В РОССИИ И ПРОБЛЕМЫ ПРОФИЛАКТИКИ...»

«АУАНАСОВА КАМИЛЛА МУСИРОВНА Перспективы и развитие идеи евразийства в современной истории Казахстана Специальность 07.00.02 – Отечественная история (История Республики Казахстан) Диссертация на соискание ученой степени доктора исторических наук Научный консультант : доктор исторических наук Кенжебаев Г.К. Республика Казахстан Алматы, 2010 СОДЕРЖАНИЕ Введение.. 1 Евразийская традиция: истоки,...»

«Горский Михаил Александрович Геометрия и комбинаторика комплексов подслов и двойственных им многогранников 01.01.04 – Геометрия и топология ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель член-корреспондент РАН, проф. В.М. Бухштабер Москва – 2014 Оглавление 1. Введение................................ 2....»

«Каслова Анастасия Александровна Метафорическое моделирование президентских выборов в России и США (2000 г.) 10.02.20 – сравнительно-историческое, типологическое и сопоставительное языкознание Диссертация на соискание ученой степени кандидата филологических наук Научные руководители: Заслуженный деятель науки РФ, доктор филологических наук,...»

«Дуплий Степан Анатольевич УДК 539.12 ПОЛУГРУППОВЫЕ МЕТОДЫ В СУПЕРСИММЕТРИЧНЫХ ТЕОРИЯХ ЭЛЕМЕНТАРНЫХ ЧАСТИЦ 01.04.02 – Теоретическая физика Диссертация на соискание ученой степени доктора физико-математических наук Харьков – 1999 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ 10 РАЗДЕЛ 1. Теория необратимых супермногообразий 1.1. Обратимые супермногообразия в терминах окрестностей 1.2. Необратимые супермногообразия.............. 1.2.1....»

«  Клочко Ирина Владимировна  ПЕДАГОГИЧЕСКИЕ УСЛОВИЯ ВОСПИТАНИЯ ПРАВОВОГО  СОЗНАНИЯ СТАРШЕКЛАССНИКОВ: ДЕЯТЕЛЬНОСТНЫ Й  ПОДХОД  13.00.01 – общая педагогика, история педагогики и образования  Диссертация  на соискание учёной степени ...»

«Удалено...»

«ОРЛОВА ЮЛИЯ ЕВГЕНЬЕВНА СТАНОВЛЕНИЕ И РАЗВИТИЕ ПЕДАГОГИЧЕСКОГО ОБРАЗОВАНИЯ РОДИТЕЛЕЙ ДОШКОЛЬНИКОВ ПО ПОДГОТОВКЕ ДЕТЕЙ К ОБУЧЕНИЮ В ШКОЛЕ (СЕРЕДИНА XVII – НАЧАЛО ХХI ВВ.) 13.00.01 – общая педагогика, история педагогики и образования диссертация на соискание ученой степени кандидата педагогических наук Москва 2014 Становление и развитие педагогического образования родителей дошкольников по подготовке детей к обучению школе (середина XVII- начало ХХI вв.). Введение..2- 1 глава....»

«ДОРОШЕНКО Станислав Иванович РАЗВИТИЕ ТЕХНОЛОГИИ РАЗРУШЕНИЯ ГОРНЫХ ПОРОД ГЕЛЕВЫМИ ВВ, ИЗГОТОВЛЕННЫМИ НА ОСНОВЕ УТИЛИЗИРУЕМЫХ БОЕПРИПАСОВ Специальность 25.00.20 Геомеханика, разрушение горных пород, рудничная аэрогазодинамика и горная теплофизика Диссертация на соискание ученой степени кандидата технических наук Научный руководитель доктор технических наук, профессор Михайлов Николай Павлович...»

«Платонов Сергей Александрович ТВЕРДОТЕЛЬНЫЕ ИМПУЛЬСНЫЕ МОДУЛЯТОРЫ ГЕНЕРАТОРНЫХ ЭЛЕКТРОВАКУУМНЫХ ПРИБОРОВ СВЧ Специальность 05.12.04 “Радиотехника, в том числе системы и устройства телевидения ” Диссертация на соискание ученой степени кандидата технических наук Научный руководитель : кандидат технических наук, доцент Казанцев В. И. Москва, 2014 2 Оглавление Основные обозначения и сокращения Введение Глава 1. Состояние вопроса и постановка...»

«Когут Екатерина Викторовна ПОЛОЖЕНИЕ ЖЕНЩИН В ПАЛЕОЛОГОВСКОЙ ВИЗАНТИИ Специальность 07.00.03 – Всеобщая история (Средние века) Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель Бибиков Михаил Вадимович, доктор исторических наук, профессор Москва — Оглавление Введение 1...»

«УДК 519.2 Лукинцова Мария Николаевна СХОДИМОСТЬ МЕР И ПРЕОБРАЗОВАНИЕ РАДОНА В БЕСКОНЕЧНОМЕРНЫХ ПРОСТРАНСТВАХ 01.01.01 вещественный, комплексный и функциональный анализ ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Москва, 2014 Оглавление Введение 3 Глава 1. Равномерно распределенные последовательности 1. Определение и вспомогательные данные 2....»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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