Раскраска графов

 

Министерство  образования и науки Российской Федерации

Государственное образовательное учреждение

Высшего профессионального  образования

КУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Физико-математический факультет

Кафедра алгебры, геометрии и ТМО

 

 

 

КУРСОВАЯ  РАБОТА

По дисциплине «Дискретная математика»

Раскраска графов

 

 

 

 

 

 

 

 

Руководитель работы ________________ «__»_______________2011 г. Исполнитель Студент гр. ___ ________________ «__»_______________2011 г.

 

 

 

 

        

 

                                  

 

Оглавление

Введение: 3

Глава I. Вершинная раскраска графа 5

1.1 Основные понятия вершинной раскраски графа. 5

1.2 Переборный алгоритм для раскраски 13

Глава II. Реберная раскраска графа 15

2.1 Раскрытие понятия правильной реберной раскраски графа. 15

2.2 Методы реберной раскраски графа 16

2.3 Задачи на графы с цветными  ребрами и вытекающие из них свойства… .22

2.4 Задача о несцепленных треугольниках  с одноцветными сторонами…..…33

Заключение………………………………………………………………………….37

Литература 38

 

Введение:

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

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

Пусть S_n — множество целых чисел от 1 до п, которые мы будем называть цветами; n-раскраской графа G назовем такое отображение множества V(G) в S_n, при котором вершины, являющиеся концами одного ребра, окрашиваются в разные цвета (т.е. таким вершинам сопоставляются разные элементы из S_n). Через N(G;n) обозначим число n-раскрасок графа G. Очевидно, что N(G;n) является графовой функцией. Ясно также, что если G имеет петли, то N(G;n)=0.

Будем считать, что для пустого множества  существует лишь одно его отображение  в S_n. Значит, если G — пустой граф, то полагаем N(G; п)=1.

Пусть G — объединение непересекающихся графов H и К. Тогда n-раскраска графа G является комбинацией какой-либо n-раскраски графа H и n-раскраски графа К, т. е.

N (G; п) = N (H; п) N (К; п).

Пусть граф G имеет звено А с концами х и у. Тогда множество всех n-раскрасок графа G можно отождествить с подмножеством n-раскрасок графа G'_A, у которых вершины х и у окрашены в разные цвета. Далее, рассматривая «сращивание» вершин хиу, заключаем, что множество всех n-раскрасок графа G_A^'' можно отождествить с подмножеством тех л-раскрасок графа G'_a, , в которых вершины х и у окрашиваются в один цвет. Таким образом,

N(G; n) = N(G'_A; n)-N(;n).

Существуют  следующие теоремы о раскраски  графа

 

 

Теорема 1:

Для произвольного графа G и любого положительного целого п число раскрасок  графа G равно Р (G; n).

Теорема 2:

Пусть G — граф без петель. Тогда P(G;n)≥0  для всех положительных целых п и при n≥|V (G)| это неравенство является строгим. Если P(G; п) = 0, то и P (G; m) = 0 для положительных целых m < n.

Первое  утверждение этой теоремы следует  из теоремы 1 и того факта, что при n≥|V(G)|, приписывая каждой вершине свой цвет, получаем n-раскраску графа G. Для завершения доказательства теоремы заметим, что m-раскраска является и n-раскраской (при m < n).

На основании  теоремы 1 P(G;λ) можно назвать хроматическим многочленом графа G. Из теоремы 2 следует, что для каждого непустого графа G без петель существует наименьшее положительное целое число n, такое, что граф G имеет n-раскраску. Оно называется хроматическим числом графа G. Граф с хроматическим числом n называется n-хроматическим.

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

 

 

Глава I. Вершинная раскраска графа

1.1 Основные понятия  вершинной раскраски графа.

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

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

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

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

 
Рис. 1. 

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

Для графов с хроматическим числом 3 такого простого описания мы не знаем. Неизвестны и простые алгоритмы, проверяющие, можно ли данный граф раскрасить в 3 цвета. Более того, задача такой  проверки (вообще, задача проверки возможности раскрасить граф в цветов при любом фиксированном ) является NP-полной.

Делая вывод  из выше сказанного приведем несколько определений вершинной раскраски графа:

 

Определение 1:

Произвольное  отображение f: V(G)→{1,2,…,k} называется вершинной k-раскраской графа G.

Пример:

Вершины графа G можно раскрасить следующим способом:

Определение 2:

Раскраска называется правильной, если для любых  смежных вершин u,v V(G)  f(u)≠f(v), т.е. никакие смежные вершины не окрашены в один цвет.

Пример: Правильная раскраска графа G может выглядеть следующим образом:

Определение 3:

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

Для графа  из предыдущего примера (G)=2, так как использование краски 3 излишне, – эту вершину можно окрасить краской 1.

Пусть G — простой граф, максимальная валентность  вершин которого равна k. Тогда G допускает (k + 1)- раскраску.

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

Рассмотрим  теорему Брукса. Пусть G— простой связный граф, максимальная валентность вершин которого равна k>2. Тогда либо G является (k + 1) -кликой, либо он имеет k-раскраску.

Доказательство. Пусть G — такой граф с наименьшим числом вершин, для которого теорема  не верна. Рассмотрим его (k + 1)-раскраску. Цвета 1, ..., k будем называть обычными, цвет (k + 1) — критическим.

Существует  так же лемма. Пусть L — цепь графа G с концами х и у. Тогда указанную выше (k + 1) -раскраску графа G можно, изменяя цвета лишь на вершинах из L, преобразовать таким образом, что критический цвет не будет приписан вершинам из L, отличным от х.

Доказательство. Расположим вершины цепи L в последовательность    (a₀, a₁, a₂ …, a_s) в которой а₀ = у и a_s — x. Перекрасим вершины этой последовательности в соответствии со следующими правилами:

1. вершине а₀ приписывается тот обычный цвет, в который не окрашены смежные с ней вершины, отличные от а₁;
2. перекрасив вершину a_j (0 <j<s - 2), вершине a_j+1 приписываем тот обычный цвет, в который не окрашены смежные с ней вершины, отличные от а_j+2;
3. перекрасив вершину a_s-1 приписываем вершине a_s тот цвет (возможно критический), в который не окрашены смежные с ней вершины.

Указанный процесс может быть осуществлен  в силу ограничения на валентность  вершин графа G. Это даст требуемую  новую (k + 1) -раскраску. А

Какова  бы ни была вершина х графа G, можно (достаточное число раз применив лемму описанную выше) построить такую (k + 1)- рас краску графа G, при которой в критический цвет окрашивается только вершина х (отказаться от критического цвета нельзя в силу выбора графа G). Эту раскраску мы назовем критической раскраской графа G с критической вершиной х.

Теперь  рассмотрим некоторые теоремы связанные  с вершинной раскраской графа

Теорема 1:

1)для любого дерева T  c (T)=2,

2)для любого n  c (O_n)=1,

3)для любого n c  (K_n)=n,

4)для любого n  (C_n)= c      

Теорема 2 (о пяти красках):

Если G – планарный граф, то c (G)≤5.

Доказательство:

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

Индуктивное предположение: допустим, что для  правильной раскраски всякого плоского графа с числом вершин <k достаточно пяти красок.

Индуктивный переход: докажем, что для правильной раскраски всякого плоского графа  с числом вершин =k достаточно пяти красок.

По следствию 11 из теоремы  Эйлера в плоском графе G существует вершина , степень которой не превосходит 5.

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

Рассмотрим  случай, когда вершина   смежна в  ровно с пятью вершинами и все они окрашены в разные цвета. Очевидно, что в других случаях (когда степень вершины  меньше 5 или среди окружения есть одноцветные) для правильной раскраски вершины  и ее окружения достаточно 5 красок.

, где вершина окрашена в цвет i.

Если  , то инверсируем в A краски (вершины цвета 1 окрашиваем цветом  3, вершины цвета 3 окрашиваем цветом 1). Правильность окраски не нарушилась, а для вершины  освободился цвет 1.

Если  , то вершина окружена циклом цвета 1,3. Значит, . Произведя в B инверсию окраски, освобождаем для вершины цвет 4.

Таким образом, граф G раскрашен правильно красками из фиксированной  правильной окраски графа . Следовательно .

Количество  способов правильной t-раскраски графа G называется хроматической функцией. Обозначают .

Например, .

Для любого G, если , то f(G, t)=0.

Для полного  графа 

 

 

Теорема 3:

Если , то .

Доказательство:

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

Теорема 4:

Если   и графы  и  имеют ровно одну общую вершину, то .

Доказательство:

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

Теорема 5:

Пусть  и  – две несмежные вершины графа G. Если , а  получается из G слиянием вершин  и , то .